移除类dp问题

移除类dp问题

移除类dp问题和平常的dp问题不一样，因为平常的dp问题都是每次做出选择直接分解成子问题，但是移除类dp问题每次的选择会改变问题的状态，所以我们需要逆向思考，给状态的定义是每次最后的选择。

题目收集：

312. 戳气球

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

• 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
• 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

输入: [3,1,5,8]
输出: 167 
解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

code

class Solution {
    public int maxCoins(int[] nums) {
        int len=nums.length;
        if (len==0)return 0;
        int[][] dp=new int[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i]=nums[i]*(i>0?nums[i-1]:1)*(i+1<len?nums[i+1]:1);
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < len-i; j++) {
                for (int k = j; k <= j+i; k++) {
                    dp[j][j+i]=Math.max(dp[j][j+i],nums[k]*(j>0?nums[j-1]:1)*(j+i+1<len?nums[j+i+1]:1)+(j>k-1?0:dp[j][k-1])+(k+1>j+i?0:dp[k+1][j+i]));
                }
            }
        }
        return dp[0][len-1];
    }
}

546. 移除盒子

给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。
当你将所有盒子都去掉之后，求你能获得的最大积分和。

示例：

输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 分) 
----> [1, 3, 3, 3, 1] (1*1=1 分) 
----> [1, 1] (3*3=9 分) 
----> [] (2*2=4 分)

提示：

• 1 <= boxes.length <= 100
• 1 <= boxes[i] <= 100

code

class Solution {
private:
    int dp[100][100][100];
public:
    int removeBoxes(vector<int>& boxes) {
        memset(dp,0,sizeof(dp));
        return calculatePoints(boxes,0,boxes.size()-1,0);
    }
    int calculatePoints(vector<int>& boxes,int l,int r,int k){
        if(l>r)return 0;
        if(dp[l][r][k]!=0)return dp[l][r][k];
        while(r>l&&boxes[r-1]==boxes[r]){
            r--;k++;
        }
        dp[l][r][k]=calculatePoints(boxes,l,r-1,0)+(k+1)*(k+1);
        for(int i=l;i<r;++i){
            if(boxes[i]==boxes[r]){
                dp[l][r][k]=max(dp[l][r][k],calculatePoints(boxes,l,i,k+1)+calculatePoints(boxes,i+1,r-1,0));
            }
        }
        return dp[l][r][k];
    }
};