LetCode 제거 상자(깊이 우선 검색, 동적 계획)

서로 다른 색깔의 상자를 제시하는데 상자의 색깔은 숫자로 표시한다. 즉, 서로 다른 숫자는 서로 다른 색깔을 표시한다.너는 모든 상자가 지워질 때까지 몇 차례의 조작을 거쳐 상자를 지울 것이다.매 라운드마다 같은 색깔의 연속 k개 상자(k>=1)를 제거할 수 있습니다. 이렇게 한 라운드가 지나면 k*k개의 포인트를 획득할 수 있습니다.모든 상자를 제거한 후에 당신이 얻을 수 있는 최대 포인트와예 1:

  :
[1, 3, 2, 2, 2, 3, 4, 3, 1]
  :
23
  :
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9  ) 
----> [1, 3, 3, 3, 1] (1*1=1  ) 
----> [1, 1] (3*3=9  ) 
----> [] (2*2=4  )

알림: 상자의 총 수는 n이 100을 넘지 않습니다.사고방식 분석: 만약에 우리가 현재 구간[i, j]을 제거해야 한다고 가정하면 boxes[i]라는 숫자를 제거하면 총 득점은 1+dp[i+1][j]이어야 한다. 그러나 제목의 요구에 따라 높은 포인트를 얻을 수 있는 사고방식은 특정한 숫자나 몇 개의 숫자를 제거한 후에 원래 연속되지 않았던 같은 숫자를 연속적으로 변화시킬 수 있기 때문이다. 동시에 제거한 숫자가 많을수록 얻은 포인트가 높기 때문이다.
그러면 [i, j] 중간에 m의 위치가 있어 boxes[i]와 boxes[m]가 같다고 가정하면 우리는 boxes[i]라는 숫자만 제거하는 것이 아니라 [i+1, m-1] 구간의 수를 직접 제거하여 boxes[i]와 boxes[m]가 직접 인접하게 하는 것도 고려해야 한다. 그러면 우리가 얻은 포인트는 dp[i+1][m-1]이다.이때 우리는 남은 boxes[i]와 boxes[m, j] 구간의 수를 처리할 수 없다. 그러나 우리는 하위 그룹 [m, j]을 처리할 수 없다. 왜냐하면 우리의 일부 정보는 우리의 dp 그룹에 포함되지 않았기 때문이다. 이런 문제는 자신이 포함하지 않는 하위 문제로 귀납되고 그 해법은 일부 하위 문제 이외의 정보에 의존한다.
이 문제에 대해 말하자면 boxes[m, j] 구간을 처리할 수 없는 것은 관건적인 정보가 부족하기 때문이다. 우리는 boxes[m] 왼쪽의 같은 숫자의 개수 k를 모른다. 이 정보를 알아야 m의 위치가 의미가 있기 때문에 우리의 dp수조는 3차원 그룹 dp[i][j][k]로 구간[i, j]에서 얻을 수 있는 최대 포인트를 나타낸다. boxes[i] 왼쪽에 k의 숫자가 있으면 그와 같다.그러면 우리의 목표는 dp[0][n-1][0]를 요구하는 것이다. 그리고 우리는 dp[i][i][k]=(1+k)*(1+k)이라는 등식을 내놓을 수 있다.
dp[i][j][k]에 대해 우리가 boxes[i]를 제거하면 (1+k)*(1+k)+dp[i+1][j][0]를 얻을 수 있다.위에서 언급한 그런 상황에 대해 어느 위치 m에 boxes[i]==boxes[m]가 있을 때 우리는 [i+1, m-1]를 먼저 제거하는 것을 고려해야 한다. 우리는 포인트 dp[i+1][m-1][0]를 얻은 다음에 나머지 부분을 처리하고 포인트 dp[m][j][k+1]를 얻는다. 여기서 k를 1점 추가한 이유는 중간 부분을 제거한 후에 원래 boxes[m]와 인접하지 않았던 boxes[i]가 지금 인접했기 때문이다. 또 양자치가 같기 때문에 k가 1을 추가해야 하기 때문이다.k의 정의는 왼쪽과 같은 숫자의 개수이기 때문이다.

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        int n = boxes.size();
        int dp[100][100][100] = {0};//dp[i][j][k]       [i, j]（ i  k    boxes[i]     ）        
        return helper(boxes, 0, n - 1, 0, dp);
    }
    //     [i, j]（ i  k    boxes[i]     ）        
    int helper(vector<int>& boxes, int i, int j, int k, int dp[100][100][100]) {
        if (j < i) {//       
            return 0;
        }
        if (dp[i][j][k] > 0) {//          
            return dp[i][j][k];
        }
        
        //   ：   res
        // [i, j]（i   k  boxes[i]     ）   [i](    k  boxes[i]     )  [i + 1, j]（i + 1   0  boxes[i + ]     ）
        //(1 + k) * (1 + k)      boxes[i]    k      ， helper(boxes, i + 1, j, 0, dp)  [i + 1, j](i + 1   0  boxes[i + 1]     )
        int res = (1 + k) * (1 + k) + helper(boxes, i + 1, j, 0, dp);
        
        //   ：  [i + 1, j]        boxes[i]     ，    [i, j]（i   k  boxes[i]     ）           
        for (int m = i + 1; m <= j; ++m) {
            if (boxes[m] == boxes[i]) {
                // [i + 1, j]       
                //    ：[i + 1, m - 1](i + 1   0  boxes[i + 1]     )helper(boxes, i + 1, m - 1, 0, dp)
                //    ： [i + 1, m - 1]   boxes[i] boxes[m]  ， boxes[m]  k + 1          helper(boxes, m, j, k + 1, dp)
                res = max(res, helper(boxes, i + 1, m - 1, 0, dp) + helper(boxes, m, j, k + 1, dp));
            }
        }
        return dp[i][j][k] = res;
    }
};

다음은 위의 깊이 우선 검색법을 추이법, 즉 동적 기획법으로 수정한다.

class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        int n = boxes.size();
        int dp[n][n][n] = {0};//dp[i][j][k]       [i, j]（ i  k    boxes[i]     ）        
        //       
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k <= i; ++k) {//   i   k  boxes[i]         
                dp[i][i][k] = (1 + k) * (1 + k);
            }   
        }
        //t     [i, j]   
        for (int t = 1; t < n; ++t) {
            for (int j = t; j < n; ++j) {//     
                int i = j - t;//      
                for (int k = 0; k <= i; ++k) {
                    //   ：   res
                    // [i, j]（i   k  boxes[i]     ）   [i](    k  boxes[i]     )  [i + 1, j]（i + 1   0  boxes[i + ]     ）
                    //(1 + k) * (1 + k)      boxes[i]    k      ， helper(boxes, i + 1, j, 0, dp)  [i + 1, j](i + 1   0  boxes[i + 1]     )
                    int res = (1 + k) * (1 + k) + dp[i + 1][j][0];
                    //   ：  [i + 1, j]        boxes[i]     ，    [i, j]（i   k  boxes[i]     ）           
                    for (int m = i + 1; m <= j; ++m) {
                        if (boxes[m] == boxes[i]) {
                            // [i + 1, j]       
                            //    ：[i + 1, m - 1](i + 1   0  boxes[i + 1]     )helper(boxes, i + 1, m - 1, 0, dp)
                            //    ： [i + 1, m - 1]   boxes[i] boxes[m]  ， boxes[m]  k + 1          helper(boxes, m, j, k + 1, dp)
                            res = max(res, dp[i + 1][m - 1][0] + dp[m][j][k + 1]);
                        }
                    }
                    dp[i][j][k] = res;//      
                }
            }
        }
        return n == 0 ? 0 : dp[0][n - 1][0];
    }
};

이상의 코드는 모두 평론 구역에서 왔고, 나는 단지 주석을 추가했을 뿐이다.