Leetcode 718

1922 단어
, ### Maximum Length of Repeated Subarray는 두 개의 수조의 최대 매칭 서브 수조를 찾아낸다. 사실은 가장 큰 문자열과 일치하고 이중순환하며 2차원 표를 구성한다. 각 칸에 대한 기입a[i]!=b[j]이라면dp[i][j]=0, 만약a[i]=b[j]이라면dp[i][j] = dp[i-1][j-1] + 1, 이것이 바로 전이 방정식이다. 요구하는 해답은 이 표의 최대 값이다.다음은 코드입니다.
class Solution {
public:
    int findLength(vector<int>& a, vector<int>& b) {
        int dp[1001][1001] = {0}, max = 0;
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                if(a[i] != b[j]) dp[i+1][j+1] = 0;
                else dp[i+1][j+1] = dp[i][j] + 1;
                if(dp[i+1][j+1] > max) max = dp[i+1][j+1];
            }
        }
        return max;
    }
};

좋은 웹페이지 즐겨찾기