Code Implementation

class Solution:
    def minimumMoves(self, 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 arr[i] == arr[j]:
                    if length == 2:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i+1][j-1]
                else:
                    dp[i][j] = float('inf')
                    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]
      

class Solution {
public:
    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 (arr[i] == arr[j]) {
                    if (len == 2) dp[i][j] = 1;
                    else dp[i][j] = dp[i+1][j-1];
                } else {
                    dp[i][j] = INT_MAX;
                    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];
    }
};
      

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 (arr[i] == arr[j]) {
                    if (len == 2) dp[i][j] = 1;
                    else dp[i][j] = dp[i+1][j-1];
                } else {
                    dp[i][j] = Integer.MAX_VALUE;
                    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];
    }
}
      

var minimumMoves = function(arr) {
    const n = arr.length;
    const dp = Array.from({length: n}, () => 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) {
            let j = i + len - 1;
            if (arr[i] === arr[j]) {
                if (len === 2) dp[i][j] = 1;
                else dp[i][j] = dp[i+1][j-1];
            } else {
                dp[i][j] = Infinity;
                for (let 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];
};
      

Problem Description

You are given an array of positive integers, arr. In one move, you can remove any contiguous subarray that forms a palindrome (reads the same forward and backward). After removal, the left and right parts of the array concatenate to form a new array. Your goal is to find the minimum number of moves required to remove the entire array.

Constraints:

• Every move must remove a contiguous palindrome subarray.
• All elements must be removed; no element can be reused.
• The array can be up to 100 elements long.

Thought Process

At first glance, the problem seems to suggest checking every possible way to remove palindromic subarrays, which could be a huge number of combinations. A brute-force approach would try all possible ways to remove palindromes, but this quickly becomes infeasible for larger arrays due to the exponential number of possibilities.

Instead, we should look for overlapping subproblems and optimal substructure—classic signs that dynamic programming (DP) can help. If we know the minimum moves needed to remove a subarray, we can use that information to solve larger subarrays. The key is to break the problem into manageable pieces where we can reuse previous results.

We also notice that if the first and last elements of a subarray are equal, and the subarray between them can be removed in some way, then the whole subarray could potentially be removed as a palindrome in one move. This insight helps us design a DP solution.

Solution Approach

We use dynamic programming to solve this problem efficiently. Here’s how the algorithm works, step by step:

1. Define DP State:
   • Let dp[i][j] represent the minimum number of moves required to remove the subarray from index i to j (inclusive).
2. Base Case:
   • If i == j (the subarray has only one element), it is always a palindrome, so dp[i][i] = 1.
3. Transition:
   • If arr[i] == arr[j], then the minimum moves for dp[i][j] can be the same as dp[i+1][j-1] (removing the inner subarray, then removing the matching ends together).
   • Otherwise, try splitting the subarray into two parts at every possible k between i and j, and take the minimum:
     • dp[i][j] = min(dp[i][k] + dp[k+1][j]) for all k in [i, j-1].
4. Iterative Computation:
   • Fill the dp table for all subarrays of increasing length (from 1 up to n).
5. Final Answer:
   • The answer is dp[0][n-1], representing the minimum moves to remove the entire array.

This approach ensures that we always use the best way to remove palindromic subarrays, and we avoid recalculating the same subproblems multiple times.

Example Walkthrough

Let's consider arr = [1, 3, 4, 1, 5].

1. Step 1: Single elements are always palindromes, so dp[i][i] = 1 for all i.
2. Step 2: For subarrays of length 2:
   • [1,3], [3,4], [4,1], [1,5] are not palindromes, so each needs 2 moves.
3. Step 3: For subarrays of length 3:
   • [1,3,4], [3,4,1], [4,1,5] are not palindromes, so try all possible splits. Each split gives 3 moves, but we check for better options.
4. Step 4: For subarray [1,3,4,1] (indices 0 to 3):
   • The first and last elements are both 1. Check if the inner subarray [3,4] can be removed in one move (it's not a palindrome), so dp[1][2]=2. Thus, dp[0][3]=dp[1][2]=2.
5. Step 5: For the whole array [1,3,4,1,5]:
   • First and last elements are not equal, so try all possible splits:
     • Split at k=0: dp[0][0] + dp[1][4] = 1 + ?
     • Split at k=1: dp[0][1] + dp[2][4] = 2 + ?
     • Split at k=2: dp[0][2] + dp[3][4] = 3 + ?
     • Split at k=3: dp[0][3] + dp[4][4] = 2 + 1 = 3
   • The minimum is 3 moves.

So, the minimum moves to remove the array [1, 3, 4, 1, 5] is 3.

Time and Space Complexity

Brute-force approach: Would try every possible order of removing palindromic subarrays, which has exponential time complexity (much greater than O(2^n)), making it infeasible for larger arrays.

Dynamic Programming approach:

• There are O(n²) subarrays, and for each subarray, we may check O(n) possible splits.
• So, total time complexity is O(n³).
• Space complexity is O(n²) to store the DP table.

This is efficient enough for n up to 100.

Summary

The Palindrome Removal problem can be solved efficiently using dynamic programming by carefully defining subproblems (dp[i][j]) and leveraging the properties of palindromes. We avoid brute-force enumeration by reusing solutions to subarrays, and we always choose the optimal split at each step. This results in a clean, elegant, and efficient O(n³) solution that demonstrates the power of DP for problems with overlapping subproblems and optimal substructure.