随想录一刷Day53——动态规划

Day53_动态规划

44. 最长公共子序列

1143. 最长公共子序列
思路：

1. dp[i][j] 表示 text1[0~i]与text2[0~j] 的最长公共子序列
2. 递推公式：

• text1[i - 1] == text[j - 1] 时 dp[i][j] = dp[i-1][j-1] + 1 ，即 text1[0~i-1]与text2[0~j-1]的最长公共子序列基础上再添加一个
• text1[i - 1] != text[j - 1] 时 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) ，即保留text1[0~i]与text2[0~j-1]或者text1[0~i+1]与text2[0~j]的最长公共子序列

3. 初始化为 dp[i][0] = 0 dp[0][j] = 0 与空串的最长公共子序列为 0
4. 遍历顺序从前往后

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[len1][len2];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

45. 不相交的线

1035. 不相交的线
思路：

其实本质就是求最长公共子序列，同上题，只能说是一模一样。

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[n1][n2];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

46. 最大子数组和

53. 最大子数组和
思路：

1. dp[i] 表示序号i之前的最大子数组的和
2. 递推公式：

• 将当前数字加入连续子数组，dp[i] = dp[i - 1] + nums[i]
• 不将当前子数组加入连续子数组，重新开启一个子数组，dp[i] = nums[i]

3. 初始化：dp[0] = nums[0] 第一个子数组的最大和为自身
4. 遍历顺序，从前往后

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