【力扣】动态规划题目之“最”系列

一、动态规划问题解决步骤

解决动态规划（Dynamic Programming，简称DP）题目的一般思路可以分为以下几个步骤：

1. 定义状态：首先，需要明确定义问题的状态。状态是描述问题的关键信息，通常包括需要被优化的变量。状态的定义应该能够反映问题的特征，并且能够通过递归或迭代来计算。
2. 定义状态转移方程：一旦状态被定义，接下来就是建立状态之间的关系，也就是状态转移方程。状态转移方程描述了如何根据已知状态计算新状态。这是动态规划问题的核心。
3. 初始化：确定初始状态的值，通常是问题中的边界条件或者基础情况。这些初始状态是动态规划算法的起点。
4. 递推或迭代计算：利用状态转移方程，从初始状态开始逐步计算出问题的最优解。这可以通过自底向上的迭代方法或自顶向下的递归方法来实现。
5. 记录路径（可选）：如果需要还原最优解的具体路径，可以在状态转移的过程中记录每个状态的来源，以便后续还原路径。
6. 返回结果：根据问题的要求，从最终状态中获取所需的最优解或最优值。
7. 优化空间复杂度（可选）：在一些情况下，可以优化动态规划算法的空间复杂度，例如只保留必要的中间状态，而不是全部记录。

二、力扣经典例题

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
1
2
3

示例 2：

输入：s = "cbbd"
输出："bb"
1
2

• 思路

1. 定义状态：定义状态dp[i][j]表示字符串s[i...j]是否为回文子串
2. 定义状态转移方程

• 如果s[i]和s[j]字符不相同，显然s[i...j]不是回文串
• 如果s[i]和s[j]字符相同
• • 如果i和j是相邻的下标，即当j-i==1时，显然s[i...j]是回文串
• • 如果i和j不是相邻的下标，则s[i...j]是否是回文串取决于s[i+1...j-1]是否是回文串

则状态转移方程：

	if (s[i] == s[j]) {
        dp[i][j] = j - i == 1 ? true : dp[i + 1][j - 1];
     } else {
        dp[i][j] = false;
     }
1
2
3
4
5

3. 初始化：每单个字符是一个回文串，所以dp[i][i]初始化为true (0<=ifalse
4. 递推或迭代计算：因为dp[i][j]取决于dp[i+1][j-1]，所以状态是从长度较短的字符串向长度较长的字符串进行转移
5. 返回结果：因为需要找到最长的回文串，所以定义一个start变量表示最长回文子串的起始下标，一个maxLen变量表示最长回文子串的长度，然后每次找到一个回文子串的时候，判断该串的长度是否大于当前最长回文子串的长度，如果更长，就更新这两个标记着最长回文子串的变量的信息。最后返回s.substr(start, maxLen)即为一个最长回文子串。

• C++ Code

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() <= 1) {
            return s;
        }
        int n = s.size();
        // 定义状态：dp[i][j]表示s[i...j]是否为回文串
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        // 初始化
        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;
        }
        int start = 0;  // 记录最长回文子串的起始下标
        int maxLen = 1; // 记录最长回文子串的长度（最少一个字符本身就是回文串）
        for (int len = 2; len <= n; ++len) {  // 注意需要从长度较短的字符串向长度较长的字符串进行转移
            for (int i = 0; i < n; ++i) {
                int j = len + i - 1;
                if (j >= n) {
                    break;
                }
                // 状态转移方程
                if (s[i] == s[j]) {
                    dp[i][j] = j - i == 1 ? true : dp[i + 1][j - 1];
                } else {
                    dp[i][j] = false;
                }
                
                // 更新最长回文子串信息
                if (dp[i][j] && j - i + 1 > maxLen) {
                    start = i;
                    maxLen = j - i + 1;
                }
            }
        }
        return s.substr(start, maxLen);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

32. 最长有效括号

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
1
2
3

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
1
2
3

示例 3：

输入：s = ""
输出：0
1
2

提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
1
2

• 思路

1. 定义状态：用dp[i]代表以第i个字符结尾的最长有效括号长度（i从0开始到n-1），例如(()，就有dp[0]=0，dp[1]=0，dp[2]=2；
2. 定义状态转移方程：

• 如果s[i]是左括号(，显然dp[i]=0，因为左括号是不可能作为一串有效括号的结尾字符【例如字符串((】
• 如果s[i]是右括号)，则根据前一个字符是左括号还是右括号，需要分情况讨论
• • 如果s[i-1]是左括号(，则dp[i]=dp[i-2]+2（i>=2），【例如字符串(())()，dp[5]=dp[3]+2=4+2=6】
• • 如果s[i-1]是右括号)，首先找到以第i-1个字符结尾的最长有效括号的前面一个字符，即s[i-dp[i-1]-1]，
• • • 如果这个字符是左括号(，那么dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]，【例如字符串()(())，dp[5]=dp[4]+2+dp[1]=2+2+2=6】
• • • 如果这个字符是右括号)，那么dp[i]=0（构不成有效括号串了）【例如)())是一个非有效的字符串】

状态转移方程简写后为：

if (s[i] == ')') {
    if (s[i - 1] == '(') {
        dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;
    } else if (s[i - 1] == ')' && i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
        dp[i] =  i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] + dp[i - 1] + 2 : dp[i - 1] + 2;
    }
}
1
2
3
4
5
6
7

3. 初始化：dp[i]=0
4. 递推或迭代计算：从i等于1开始遍历，因为至少两个字符才能组成有效括号，所以dp[0]一定是0
5. 返回结果：每次计算dp[i]的过程同时更新maxLen

• C++ Code

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n, 0);
        int maxLen = 0;
        for (int i = 1; i < n; ++i) {
            if (s[i] == '(') {
                continue;
            }
            if (s[i - 1] == '(') {
                dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;
            } else if (s[i - 1] == ')' && i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] =  i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] + dp[i - 1] + 2 : dp[i - 1] + 2;
            }
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
1
2
3

示例 2：

输入：nums = [1]
输出：1
1
2

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23
1
2

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1
2

• 思路

1. 定义状态：用dp[i]表示以第i个数结尾的数组的最大和
2. 定义状态转移方程：

   dp[i] = max(dp[i - 1] + nums[i], nums[i]); (i>=1)
   1

   如果第i个数加上以第i-1个数结尾的数组的最大和比第i个数本身还要小，那还不如不加。
3. 初始化：dp[0]=nums[0]
4. 递推或迭代计算：从i=1开始遍历到n-1
5. 返回结果：设定一个maxSum，初始值为nums[0]，后面的每轮遍历中都更新maxSum的大小

• C++ Code
• • dp数组版：

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int n = nums.size();
            // dp[i]表示以第i个数结尾的数组的最大连续子数组的和
            vector<int> dp(n, 0);
            // 初始化
            dp[0] = nums[0];
            int maxSum = nums[0];
            for (int i = 1; i < n; ++i) {
                dp[i] = max(dp[i - 1] + nums[i], nums[i]);
                maxSum = max(maxSum, dp[i]);
            }
            return maxSum;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15

• • 简化版：dp[i]只会用到dp[i-1]的数据，所以可以直接使用一个变量sum替代就好。

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int n = nums.size();
            int sum = nums[0];
            int maxSum = sum;
            for (int i = 1; i < n; ++i) {
                sum = max(sum + nums[i], nums[i]);
                maxSum = max(maxSum, sum);
            }
            return maxSum;
        }
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13