C++에서 회문 제거

arr이라는 정수 배열이 있다고 가정하고, 이제 한 번의 이동으로 i <=j인 인덱스 i에서 j까지 회문 하위 배열을 선택하고 주어진 배열에서 해당 하위 배열을 제거할 수 있습니다. 하위 배열을 제거한 후 해당 하위 배열의 왼쪽과 오른쪽에 있는 요소가 제거로 인해 남은 간격을 채우기 위해 이동한다는 점을 명심해야 합니다. 배열에서 모든 숫자를 제거하는 데 필요한 최소 이동 횟수를 찾아야 합니다.

따라서 입력이 arr =[1,3,4,1,5]와 같으면 출력은 3이 됩니다. 이 시퀀스에서 제거할 수 있으므로 [4]를 제거한 다음 [1,3,1]을 제거한 다음 [5]를 제거합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=arr의 크기

• (n + 1) x (n + 1) 크기의 2D 배열 dp 하나 정의

• 초기화 l :=1의 경우, l <=n일 때 업데이트(l을 1만큼 증가), 수행 -

  • initialize i :=0, j :=l - 1, j

    • l이 1과 같으면 -

      • dp[i, j] :=1

    • 그렇지 않으면

      • dp[i, j] :=1 + dp[i + 1, j]

      • i + 1

        • dp[i, j] :=dp[i, j] 및 1 + dp[i + 2, j]의 최소값

      • 초기화 k :=i + 2의 경우 k <=j일 때 업데이트(k를 1만큼 증가), −

        • arr[i]가 arr[k]와 같으면 -

          • dp[i, j] :=dp[i, j] 및 dp[i + 1, k - 1] + dp[k + 1, j]의 최소값

• 반환 dp[0, n - 1]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minimumMoves(vector<int>& arr) {
      int n = arr.size();
      vector<vector<int> > dp(n + 1, vector<int>(n + 1));
      for (int l = 1; l <= n; l++) {
         for (int i = 0, j = l - 1; j < n; i++, j++) {
            if (l == 1) {
               dp[i][j] = 1;
            } else {
               dp[i][j] = 1 + dp[i + 1][j];
               if (i + 1 < n && arr[i] == arr[i + 1])
               dp[i][j] = min(dp[i][j], 1 + dp[i + 2][j]);
               for (int k = i + 2; k <= j; k++) {
                  if (arr[i] == arr[k]) {
                     dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j]);
                  }
               }
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2};
   cout << (ob.minimumMoves(v));
}

입력

[1,2]

출력

2