Problem Explanation

We are given an integer array, and we are allowed to remove palindromic subarrays in one move. After removing a subarray, the remaining parts of the array move towards each other to fill the gap.

The task is to find the minimum number of moves needed to remove all numbers from the array.

Approach

This problem can be solved using dynamic programming.

We define a 2D DP array dp[i][j] to represent the minimum number of moves to remove all numbers from the subarray arr[i..j].

The base cases for our DP are when the subarray length is 1 or 2. When the subarray length is 1, it's obviously a palindrome (since it only contains one element), so we fill 1 in our DP array. When the subarray length is 2, if the two numbers are the same (make a palindrome), we fill 1 in our DP array, otherwise, we fill 2 (each of them is a palindrome of itself).

For subarrays of length more than 2, we have two cases:

1. If arr[i] and arr[j] are the same, we can consider them as outer parts of a possible palindrome. So, we fill dp[i][j] as dp[i+1][j-1] (The minimum number of moves for the subarray arr[i+1..j-1]).

2. We also need to consider all possible partitions of the array, and choose the one that leads to the minimum number of moves. So, we iterate over the subarray and choose the index k that results in the minimum moves, dp[i][k] + dp[k+1][j].

At the end of our DP process, dp[0][n-1] will be our answer, the minimum number of moves to remove all elements from the whole array.

Example

Let's walk through an example: arr = [1,3,4,1,5]

DP array after initialization and base cases:

1 2 100 100 100 100 1 100 100 100 100 100 1 100 100 100 100 100 1 100 100 100 100 100 1

DP array after full DP process:

1 2 2 2 3 100 1 2 2 2 100 100 1 2 2 100 100 100 1 2 100 100 100 100 1

So, 3 is the minimum number of moves needed.

Solution

Python Solution

1
2python
3class Solution:
4    def minimumMoves(self, arr: List[int]) -> int:
5        n = len(arr)
6        dp = [[n] * n for _ in range(n)]
7        for i in range(n):
8            dp[i][i] = 1
9        for i in range(n-1):
10            dp[i][i+1] = 1 if arr[i] == arr[i+1] else 2
11        for length in range(3, n+1):
12            for i in range(n-length+1):
13                j = i + length - 1
14                if arr[i] == arr[j]:
15                    dp[i][j] = dp[i+1][j-1]
16                for k in range(i, j):
17                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
18        return dp[0][n-1]

Java Solution

1
2java
3class Solution {
4    public int minimumMoves(int[] arr) {
5        int n = arr.length;
6        int[][] dp = new int[n][n];
7        for(int i=0; i<n; i++) {
8            dp[i][i] = 1;
9        }
10        for(int i=0; i<n-1; i++) {
11            dp[i][i+1] = arr[i] == arr[i+1] ? 1 : 2;
12        }
13        for(int length=3; length<=n; length++) {
14            for(int i=0; i<=n-length; i++) {
15                int j = i + length - 1;
16                if(arr[i] == arr[j]) {
17                    dp[i][j] = dp[i+1][j-1];
18                }
19                for(int k=i; k<j; k++) {
20                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j]);
21                }
22            }
23        }
24        return dp[0][n-1];
25    }
26}

Javascript Solution

1
2javascript
3var minimumMoves = function(arr) {
4    let n = arr.length;
5    let dp = Array(n).fill().map(() => Array(n).fill(n));
6    for(let i=0; i<n; i++) {
7        dp[i][i] = 1;
8    }
9    for(let i=0; i<n-1; i++) {
10        dp[i][i+1] = arr[i] === arr[i+1] ? 1 : 2;
11    }
12    for(let length=3; length<=n; length++) {
13        for(let i=0; i<=n-length; i++) {
14            let j = i + length - 1;
15            if(arr[i] === arr[j]) {
16                dp[i][j] = dp[i+1][j-1];
17            }
18            for(let k=i; k<j; k++) {
19                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j]);
20            }
21        }
22    }
23    return dp[0][n-1];
24};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int minimumMoves(vector<int>& arr) {
6        int n = arr.size();
7        vector<vector<int>> dp(n, vector<int>(n, n));
8        for(int i=0; i<n; i++) {
9            dp[i][i] = 1;
10        }
11        for(int i=0; i<n-1; i++) {
12            dp[i][i+1] = arr[i]==arr[i+1] ? 1 : 2;
13        }
14        for(int length=3; length<=n; length++) {
15            for(int i=0; i<=n-length; i++) {
16                int j = i + length - 1;
17                if(arr[i] == arr[j]) {
18                    dp[i][j] = dp[i+1][j-1];
19                }
20                for(int k=i; k<j; k++) {
21                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
22                }
23            }
24        }
25        return dp[0][n-1];
26    }
27};

C# Solution

1
2csharp
3public class Solution {
4    public int MinimumMoves(int[] arr) {
5        int n = arr.Length;
6        int[,] dp = new int[n, n];
7        for(int i=0; i<n; i++) {
8            dp[i, i] = 1;
9        }
10        for(int i=0; i<n-1; i++) {
11            dp[i, i+1] = arr[i]==arr[i+1] ? 1 : 2;
12        }
13        for(int length=3; length<=n; length++) {
14            for(int i=0; i<=n-length; i++) {
15                int j = i + length - 1;
16                if(arr[i] == arr[j]) {
17                    dp[i, j] = dp[i+1, j-1];
18                }
19                for(int k=i; k<j; k++) {
20                    dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k+1, j]);
21                }
22            }
23        }
24        return dp[0, n-1];
25    }
26}

Solution Explained

We have already initialized our DP array with base solutions for subarrays of length 1 and 2, and now we need to fill out this array for all subarrays of length more than 2.

We start with smaller lengths and gradually move to larger lengths. For each length, we traverse the array and solve the subproblem for each subarray of that length.

For each subarray arr[i..j], we know that if arr[i] and arr[j] are the same, they form outer parts of a possible palindrome and we can remove them in one move along with the inner part arr[i+1..j-1] which only requires dp[i+1][j-1] moves.

But in case arr[i] and arr[j] are not the same, we need to consider all possible partitions of this subarray, and each partition requires one move to remove it. So, we iterate over this subarray to find the partition index k that results in the minimum moves, dp[i][k] + dp[k+1][j].

In this way, we fill our DP array to find the minimum number of moves for all subarrays. The value dp[0][n-1] gives us the minimum number of moves needed to remove all numbers from the whole array.

This dynamic programming approach has a time complexity of O(n^3) and space complexity of O(n^2) where n is the size of the array.

This is a great problem to practice dynamic programming with subarray based problems along with the concept of palindromic subarrays. Note that careful initialization of the DP array and correct order of filling up dynamic programming table i.e from smaller subproblems to larger subproblems is crucial for the correctness and efficiency of the solution.