# 1246. Palindrome Removal
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/palindrome-removal/
## 思路
ppt里面写错了 如果```i==j``` 那么```dp[i][j]=1```
如果缩小到子问题之后找不到突破口，就从子问题的最后一个元素下手
例如这道题就是在子问题里面找和最后一个元素相等的元素
如果找到了一个元素 ```arr[k]```和```arr[j]```相等 那么说明这两个元素可以和```arr[k+1][j-1]```同一批被消掉(例如如果是```[1,2,3,1]```, 只考虑```[2,3]```，会发现需要两次操作，但是如果删完3之后，```[1,2,1]```可以在一次操作里面被删掉)
这里之所以需要写```Math.max(1, dp[k+1][j-1])```是因为有可能```k+1```和```j-1```本来就是相邻的 那么还是需要一个操作才能把他们消掉的
## Code

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