# 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 class Solution { public: int minimumMoves(vector& arr) { const int n = arr.size(); // dp[i][j] := min # of moves to remove all numbers from arr[i..j] vector> dp(n, vector(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 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] := min # 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 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] := min # 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 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]