[리트코드]

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3807/

 

두 배열에서 가장 긴 공통 수열을 찾는 문제였다. dp를 이용해서 풀었다.

dp식은 nums1[i-1]==nums2[j-1]일때, dp[i][j] = dp[i-1][j-1]. 

 

코드

int findLength(vector<int>& nums1, vector<int>& nums2) {
    int M = 0;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            if(nums1[i-1] == nums2[j-1]){
                dp1[i][j] = dp1[i-1][j-1] + 1;
                M = max(M, dp1[i][j]);
            }
        }
    }
    return M;
}