Description#
You are given an integer array arr.
In one move, you can select a palindromic subarray arr[i], arr[i + 1], ..., arr[j] where i <= j, and remove that subarray from the given array. Note that after removing a subarray, the elements on the left and on the right of that subarray move to fill the gap left by the removal.
Return the minimum number of moves needed to remove all numbers from the array.
Example 1:
Input: arr = [1,2]
Output: 2
Example 2:
Input: arr = [1,3,4,1,5]
Output: 3
Explanation: Remove [4] then remove [1,3,1] then remove [5].
Constraints:
1 <= arr.length <= 1001 <= arr[i] <= 20
Solutions#
Solution 1: Dynamic Programming (Interval DP)#
We define $f[i][j]$ as the minimum number of operations required to delete all numbers in the index range $[i,..j]$. Initially, $f[i][i] = 1$, which means that when there is only one number, one deletion operation is needed.
For $f[i][j]$, if $i + 1 = j$, i.e., there are only two numbers, if $arr[i]=arr[j]$, then $f[i][j] = 1$, otherwise $f[i][j] = 2$.
For the case of more than two numbers, if $arr[i]=arr[j]$, then $f[i][j]$ can be $f[i + 1][j - 1]$, or we can enumerate $k$ in the index range $[i,..j-1]$, take the minimum value of $f[i][k] + f[k + 1][j]$. Assign the minimum value to $f[i][j]$.
The answer is $f[0][n - 1]$.
The time complexity is $O(n^3)$, and the space complexity is $O(n^2)$. Where $n$ is the length of the array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def minimumMoves(self, arr: List[int]) -> int:
n = len(arr)
f = [[0] * n for _ in range(n)]
for i in range(n):
f[i][i] = 1
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
if i + 1 == j:
f[i][j] = 1 if arr[i] == arr[j] else 2
else:
t = f[i + 1][j - 1] if arr[i] == arr[j] else inf
for k in range(i, j):
t = min(t, f[i][k] + f[k + 1][j])
f[i][j] = t
return f[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
| class Solution {
public int minimumMoves(int[] arr) {
int n = arr.length;
int[][] f = new int[n][n];
for (int i = 0; i < n; ++i) {
f[i][i] = 1;
}
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (i + 1 == j) {
f[i][j] = arr[i] == arr[j] ? 1 : 2;
} else {
int t = arr[i] == arr[j] ? f[i + 1][j - 1] : 1 << 30;
for (int k = i; k < j; ++k) {
t = Math.min(t, f[i][k] + f[k + 1][j]);
}
f[i][j] = t;
}
}
}
return f[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
| class Solution {
public:
int minimumMoves(vector<int>& arr) {
int n = arr.size();
int f[n][n];
memset(f, 0, sizeof f);
for (int i = 0; i < n; ++i) {
f[i][i] = 1;
}
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (i + 1 == j) {
f[i][j] = arr[i] == arr[j] ? 1 : 2;
} else {
int t = arr[i] == arr[j] ? f[i + 1][j - 1] : 1 << 30;
for (int k = i; k < j; ++k) {
t = min(t, f[i][k] + f[k + 1][j]);
}
f[i][j] = t;
}
}
}
return f[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
| func minimumMoves(arr []int) int {
n := len(arr)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
f[i][i] = 1
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if i+1 == j {
f[i][j] = 2
if arr[i] == arr[j] {
f[i][j] = 1
}
} else {
t := 1 << 30
if arr[i] == arr[j] {
t = f[i+1][j-1]
}
for k := i; k < j; k++ {
t = min(t, f[i][k]+f[k+1][j])
}
f[i][j] = t
}
}
}
return f[0][n-1]
}
|
