廣東一站式網站建設報價百度網址大全舊版安裝
思路就是建立一個二維的dp數組,只要nums1[i]==nums2[j](nums1和nums2出現重復元素就置1? 并加上左上角的值)
為什么代碼是nums1 i-1和nums2 i-1
答:因為i和j以1為初始值開始遍歷的
為什么要這么做并且為什么要加dp【i-1】【j-1】?
我們觀察dp數組,發(fā)現dp【i】【j】的左上角為1就是連續(xù)的重復子串,那就將所有的dp【i】【j】都加上左上角的值,ans再遍歷的過程中同時取最大值就是我們要的答案
這也是為什么我們會在dp[i][j]多加上一行一列的原因,防止加上后越界
class Solution {static const int N = 1e3+7; int dp[N][N];
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int ans=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]=1+dp[i-1][j-1];ans=max(ans,dp[i][j]);}}return ans;}
};