https://leetcode.com/problems/maximum-length-of-repeated-subarray/
2개의 정수형 배열이 주어지고 두 배열의 부분집합중 길이가 최대인 부분집합을 구하는 문제이다.
이 문제를 여러가지 방식으로 풀 수 있겠지만, 그 중에 DP를 사용해서 풀어보았다.
DP의 메모이제이션을 활용하였다.
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int max = 0;
int[][] dp = new int[nums1.length][nums2.length];
for(int i = 0; i < nums1.length; i++) {
for(int j = 0; j < nums2.length; j++) {
if(nums1[i] == nums2[j]) {
if(i == 0 || j == 0 || dp[i-1][j-1] == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i-1][j-1] + 1;
max = Math.max(max, dp[i][j]);
}
}
}
}
return max;
}
}num1배열에서 시작해서 num2배열을 하나씩 순회하며 두 배열의 값이 같을 시 +1 해주는 로직이다.
최대 길이의 부분집합을 구하는 것이기 때문에 dp 배열의 하나 전의 인덱스(dp[i-1][j-1])가 0이 아니라면 (값이 존재한다면) 이어진다는 의미이다.
