Palindrome Removal

hard interval dp palindrome

Problem

You are given an integer array arr. In one move you may select any palindromic subarray arr[i..j] (1 <= i <= j <= arr.length) and remove it; remaining elements close the gap. Return the minimum number of moves needed to remove all numbers from the array.

Inputarr = [1, 3, 4, 1, 5]

Output3

Remove [4] then remove [1, 3, 1] (now adjacent) then remove [5]. Three moves total.

arr (comma-separated)

def minimum_moves(arr):
    n = len(arr)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if length == 2:
                dp[i][j] = 1 if arr[i] == arr[j] else 2
            else:
                best = 10 ** 9
                if arr[i] == arr[j]:
                    best = dp[i + 1][j - 1]
                for k in range(i, j):
                    best = min(best, dp[i][k] + dp[k + 1][j])
                dp[i][j] = best
    return dp[0][n - 1]

function minimumMoves(arr) {
  const n = arr.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = 1;
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      if (len === 2) {
        dp[i][j] = arr[i] === arr[j] ? 1 : 2;
      } else {
        let best = Infinity;
        if (arr[i] === arr[j]) best = dp[i + 1][j - 1];
        for (let k = i; k < j; k++) best = Math.min(best, dp[i][k] + dp[k + 1][j]);
        dp[i][j] = best;
      }
    }
  }
  return dp[0][n - 1];
}

class Solution {
    public int minimumMoves(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = 1;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (len == 2) {
                    dp[i][j] = arr[i] == arr[j] ? 1 : 2;
                } else {
                    int best = Integer.MAX_VALUE;
                    if (arr[i] == arr[j]) best = dp[i + 1][j - 1];
                    for (int k = i; k < j; k++) best = Math.min(best, dp[i][k] + dp[k + 1][j]);
                    dp[i][j] = best;
                }
            }
        }
        return dp[0][n - 1];
    }
}

int minimumMoves(vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (len == 2) {
                dp[i][j] = arr[i] == arr[j] ? 1 : 2;
            } else {
                int best = INT_MAX;
                if (arr[i] == arr[j]) best = dp[i + 1][j - 1];
                for (int k = i; k < j; k++) best = min(best, dp[i][k] + dp[k + 1][j]);
                dp[i][j] = best;
            }
        }
    }
    return dp[0][n - 1];
}

Explanation

This is an interval DP: we figure out the answer for small chunks of the array first, then build up to the whole thing. Here dp[i][j] means "the fewest moves to delete everything from index i to j".

The base cases are easy. A single element dp[i][i] takes 1 move. A pair takes 1 move if both numbers are equal (it is already a palindrome) and 2 moves otherwise.

For longer intervals there are two ideas. If the two ends match (arr[i] == arr[j]), they can ride out together with whatever clears the inside, so we can use dp[i+1][j-1]. We also try every split point k and combine dp[i][k] + dp[k+1][j], keeping the smallest total.

Example: [1, 3, 4, 1, 5]. Remove [4] (1 move), which makes [1, 3, 1] adjacent — that is a palindrome, remove it (1 move) — then remove [5] (1 move). Total 3 moves, which is dp[0][4].

The final answer is dp[0][n-1], the cost to clear the entire array.

Time: O(n³) Space: O(n²)