718. 最长重复子数组

两种dp定义不同，初始化不同

注意二者的if语句

第一种（以i-1结尾） if ( nums1[i - 1] == nums2[j - 1] ) dp[i][j] = dp[i - 1][j - 1] + 1;

第二种（以i结尾） if ( nums1[i] == nums2[j] ) dp[i][j] = dp[i - 1][j - 1] + 1;

class Solution {
public:
//dp[i][j] 以i - 1 结尾的nums1 以 j - 1 结尾的nums2 相同的最大长度int findLength(vector<int>& nums1, vector<int>& nums2) {int result = 0;vector<vector<int>> dp(nums1.size() + 1 , vector<int> (nums2.size() + 1 , 0));for ( int i = 1 ; i <= nums1.size() ; i++ ) {for ( int j = 1 ; j <= nums2.size() ; j++ ) {if ( nums1[i - 1] == nums2[j - 1] ) dp[i][j] = dp[i - 1][j - 1] + 1;if ( dp[i][j] > result ) result = dp[i][j];}}return result;}
};

class Solution {
public:
//dp[i][j] 以i 结尾的nums1 以 j 结尾的nums2 相同的最大长度int findLength(vector<int>& nums1, vector<int>& nums2) {int result = 0;vector<vector<int>> dp(nums1.size() , vector<int> (nums2.size() , 0));for ( int i = 0 ; i < nums1.size() ; i++ ) if ( nums2[0] == nums1[i] ) {dp[i][0] = 1;result = 1;}for ( int j = 0 ; j < nums2.size() ; j++ ) if ( nums1[0] == nums2[j] ) {dp[0][j] = 1;result = 1;} for ( int i = 1 ; i < nums1.size() ; i++ ) {for ( int j = 1 ; j < nums2.size() ; j++ ) {if ( nums1[i] == nums2[j] ) dp[i][j] = dp[i - 1][j - 1] + 1;if ( dp[i][j] > result ) result = dp[i][j];}}return result;}
};

1143.最长公共子序列

注意if 中是 i - 1；

这里不用要求是连续，所以dp【i】【j】不管是否相等，都要继承前面的，也就有了else中的dp【i】【j】 = max(dp[i][j - 1] , dp[i - 1][j]);

class Solution {
public:
//dp[i][j] 以【0，i-1】的text1 和 【0，j-1】的text2 的最长公共子序列的长度int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp( text1.size() + 1 , vector<int> (text2.size() + 1 , 0));for ( int i = 1 ; i <= text1.size() ; i++ ) {for ( int j = 1 ; j <= text2.size() ; 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[text1.size()][text2.size()];}
};

1035.不相交的线

此题与上一题 1143.最长公共子序列只是题目描述不同

解法一样

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
//dp[i][j] 以【0，i-1】的text1 和 【0，j-1】的text2 的最长公共子序列的长度vector<vector<int>> dp( nums1.size() + 1 , vector<int> (nums2.size() + 1 , 0));for ( int i = 1 ; i <= nums1.size() ; i++ ) {for ( int j = 1 ; j <= nums2.size() ; 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[nums1.size()][nums2.size()];}
};