Skip to content

1246. Palindrome Removal 👍

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int minimumMoves(vector<int>& arr) {
    const int n = arr.size();
    // dp[i][j] := the minimum number of moves to remove all numbers from
    // arr[i..j]
    vector<vector<int>> dp(n, vector<int>(n, n));

    for (int i = 0; i < n; ++i)
      dp[i][i] = 1;

    for (int i = 0; i + 1 < n; ++i)
      dp[i][i + 1] = arr[i] == arr[i + 1] ? 1 : 2;

    for (int d = 2; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        // Remove arr[i] and arr[j] within the move of removing
        // arr[i + 1..j - 1]
        if (arr[i] == arr[j])
          dp[i][j] = dp[i + 1][j - 1];
        // Try all the possible partitions.
        for (int k = i; k < j; ++k)
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
      }

    return dp[0][n - 1];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int minimumMoves(int[] arr) {
    final int n = arr.length;
    // dp[i][j] := the minimum number of moves to remove all numbers from arr[i..j]
    int[][] dp = new int[n][n];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, n));

    for (int i = 0; i < n; ++i)
      dp[i][i] = 1;

    for (int i = 0; i + 1 < n; ++i)
      dp[i][i + 1] = arr[i] == arr[i + 1] ? 1 : 2;

    for (int d = 2; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        // Remove arr[i] and arr[j] within the move of removing
        // arr[i + 1..j - 1]
        if (arr[i] == arr[j])
          dp[i][j] = dp[i + 1][j - 1];
        // Try all the possible partitions.
        for (int k = i; k < j; ++k)
          dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
      }

    return dp[0][n - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def minimumMoves(self, arr: list[int]) -> int:
    n = len(arr)
    # dp[i][j] := the minimum number of moves to remove all numbers from arr[i..j]
    dp = [[n] * n for _ in range(n)]

    for i in range(n):
      dp[i][i] = 1

    for i in range(n - 1):
      dp[i][i + 1] = 1 if arr[i] == arr[i + 1] else 2

    for d in range(2, n):
      for i in range(n - d):
        j = i + d
        # Remove arr[i] and arr[j] within the move of removing
        # arr[i + 1..j - 1]
        if arr[i] == arr[j]:
          dp[i][j] = dp[i + 1][j - 1]
        # Try all the possible partitions.
        for k in range(i, j):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])

    return dp[0][n - 1]