最长重复子数组
动态规划
- 确定dp数组含义
dp[i][j] ：以下标i - 1为结尾的A（A的第i个元素），和以下标j - 1为结尾的B（B的第j个元素），最长重复子数组长度为dp[i][j]。 - 确定递推公式
- 根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。
即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
初始化
- dp[0][0]、dp[i][0]、dp[0][j]都为0，因为下标为0意味着没有元素进行匹配，因此匹配的个数也是0。从dp[i][j]开始有意义，即nums1和nums2都拿出了一个元素
class Solution { public: int findLength(vector<int>& nums1, vector<int>& nums2) { //dp数组下标i和j意味着第几个元素，因此长度+1 vector<vector<int>> dp(nums1.size()+1 , vector<int>(nums2.size()+1,0)); int result = 0 ; for(int i=0 ; i<nums1.size() ;i++) { for(int j=0 ;j<nums2.size();j++) { if(nums1[i] == nums2[j]) dp[i+1][j+1] = dp[i][j]+1; if(dp[i+1][j+1] > result) result = dp[i+1][j+1]; } } // for(int i=0 ; i<=nums1.size() ;i++) // { // for(int j=0 ;j<=nums2.size();j++) // { // if(dp[i][j] > result) result = dp[i][j]; // cout<<dp[i][j]<<' '; // } // cout<<endl; // } return result; } };
二刷
class Solution { public: int findLength(vector<int>& nums1, vector<int>& nums2) { vector<vector<int>> dp(nums1.size() , vector<int>(nums2.size(),0)); int result = 0; for(int i=0 ; i<nums1.size() ; i++) { if(nums1[i] == nums2[0]) dp[i][0] = 1; if(dp[i][0] > result) result = dp[i][0]; } for(int j=0 ; j<nums2.size() ; j++) { if(nums1[0] == nums2[j]) dp[0][j] = 1; if(dp[0][j] > result) result = dp[0][j]; } 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]; } } // for(int i=0 ; i<nums1.size() ; i++) // { // for(int j=0 ; j<nums2.size() ;j++) // { // cout<<dp[i][j]<<' '; // } // cout<<endl; // } return result; } };
