LeetCode 第53天 | 1143. 最长公共子序列 1035. 不相交的线 53. 最大子数组和 PTA一些注意点 动态规划

1143. ���长公共子序列

最长公共子序列和最长公共子数组的区别在于，dp中子序列可以不连续，可以从左上（text1[i-1] == text2[j-1]）推出，也能从左边或者上边（取最大值）推出；公共子数组只能从左上角推出。

class Solution {public:    int longestCommonSubsequence(string text1, string text2) {        vector dp(text1.size()+1, vector(text2.size()+1, 0));        for (int i = 1; i             for (int j = 1; j                 // dp整体向右下移动一个                if (text1[i-1] == text2[j-1]) {                    // 如果当前值相等，直接从左上角推                    dp[i][j] = dp[i-1][j-1]+1;                }                else {                    // 如果不相等，从左边或者上边取最大值推下来                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);                }            }        }        return dp[text1.size()][text2.size()];    }};public:    int maxUncrossedLines(vector        // 笑***，根本想不出来就是最长公共子序列        vector            for (int j = 1; j                 if (nums1[i-1] == nums2[j-1]) {                    dp[i][j] = dp[i-1][j-1]+1;                }                else {                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);                }            }         }        return dp[nums1.size()][nums2.size()];    }};public:    int maxSubArray(vector        // 贪心        // int res =  INT_MIN;        // int count = 0;        // for (int i = 0; i