, ### 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;
}
};