博客

题目





思路



使用区间动态规划



dp[i][j]表示删除区间(i,j)子数组的最小操作次数



1.删除单字符只需要操作一次

dp[i][i] = 1;

2.删除两个字符时，若两字符相等，则最少操作一次，不等，则最少操作两次。

3.当arr[i] == arr[j]时，最直接的想法就是判断[i+1][j-1]是否相等

因此很容易写出：

dp[i][j] = dp[i+1][j-1];

但是，对于[1,3,1,1,2,3,2,1]这种存在两个回文子数组时，这样的写法就会出错，此时最少操作次数应该通过dp[i][k]+dp[k+1][j]获得。

因此，修改为：

dp[i][j] = Math.min(dp[i+1][j-1],dp[i][k]+dp[k+1][j]);（i <= k < j）

4.当arr[i] != arr[j]时，有

dp[i][j] = Math.min(dp[i][j],dp[i][k]+dp[k+1][j]);

5.如何控制循环条件：

当我们需要求dp[i][j]的时候，dp[i+1][j-1]需要已知

因此i+1比i更早获得，i降序；j-1比j早获得，j升序。

6.我们在初始化时，new int[][]，此时dp初始值为0，

在Math.min(dp[i][j],dp[i][k]+dp[k+1][j])时就会出错，因此可以将dp[][]赋初值为MAX_VALUE，或者使用一个临时变量min来记录，最后再dp[i][j]=min。

具体代码

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