nums라는 숫자 목록이 있다고 가정합니다. 이제 회문인 일부 하위 목록을 삭제하는 작업을 고려해 보겠습니다. 목록이 비어 있도록 필요한 최소 작업 수를 찾아야 합니다.
따라서 입력이 nums =[6, 2, 4, 4, 2, 10, 6]과 같으면 출력은 2가 됩니다. 하위 목록 [2, 4, 4, 2]를 먼저 제거한 다음 목록은 [6, 10, 6]과 같습니다. 이것도 회문이므로 목록을 비우려면 제거하십시오.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
105 x 105 크기의 배열 dp를 정의합니다.
-
dfs() 함수를 정의하면 i, j, 배열 v,
가 필요합니다. -
ret :=inf
-
i> j이면 -
-
0 반환
-
-
i가 j와 같으면 -
-
1 반환
-
-
j - i가 1과 같으면 -
-
return (v[i]가 v[j]와 같으면 1, 그렇지 않으면 2)
-
-
i + 1 <=j이고 v[i]가 v[i + 1]과 같으면 -
-
ret :=1 + dfs(i + 2, j, v)
-
-
dp[i, j]가 -1과 같지 않으면 -
-
반환 dp[i, j]
-
-
ret :=(ret, 1 + (dfs(i + 1, j, v) 및 dfs(i, j - 1, v))의 최소값)
-
v[i]가 v[j]와 같으면 -
-
ret :=ret 및 dfs(i + 1, j - 1, v)의 최소값
-
-
k 초기화의 경우:=i + 2, k
-
v[i]가 v[k]와 같으면 &minnus;
-
ret :=ret 및 dfs((i + 1, k - 1, v) + dfs(k + 1, j, v))
의 최소값
-
-
-
반환 dp[i, j] =ret
-
주요 방법에서 다음을 수행하십시오 -
-
dp를 -1로 채우기
-
n :=숫자 크기
-
반환 dfs(0, n - 1, 숫자)
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
int dp[105][105];
int dfs(int i,int j, vector <int>& v){
int ret= INT_MAX;
if(i > j)
return 0;
if(i == j)
return 1;
if(j - i == 1){
return v[i] == v[j] ? 1 : 2;
}
if(i + 1 <= j && v[i] == v[i + 1]){
ret = 1 + dfs(i + 2, j, v);
}
if(dp[i][j] != -1) return dp[i][j];
ret = min({ret, 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v))});
if(v[i] == v[j]){
ret = min(ret, dfs(i + 1, j - 1, v));
}
for(int k = i + 2; k < j; k++){
if(v[i] == v[k]){
ret = min(ret, dfs(i + 1, k - 1, v) + dfs(k + 1, j, v));
}
}
return dp[i][j] = ret;
}
int solve(vector<int>& nums) {
memset(dp , -1, sizeof dp);
int n = nums.size();
return dfs(0, n - 1, nums);
}
int main(){
vector<int> v = {6, 2, 4, 4, 2, 10, 6};
cout << solve(v);
} 입력
{6, 2, 4, 4, 2, 10, 6} 출력
2