刷题笔记9-dp应用

一、股票问题(*)

188. 买卖股票的最佳时机 IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

labuladong算法秘籍中使用了【三个状态】（三维dp数组）

1. 第几天
2. 手中是否持有股票
3. 最大交易限制（最大交易限制只在买入股票时减一）

// dp[i][j][k] 意味着在第i天，手中持有(j=1)或不持有(j=0)股票，最大交易限制为k情况下的最大利润

状态转移方程

dp[i][0][k] = Math.max(
    dp[i-1][0][k],  // 第i天 不买入不卖出: 第i-1天也没有股票，交易限制还是k
    dp[i-1][1][k]+prices[i-1] // 第i天 卖出: 第i-1天有股票，交易限制还是k
);
dp[i][1][k] = Math.max(
    dp[i-1][1][k], // 第i天 不买入不卖出: 第i-1天有股票，交易限制为k
    dp[i-1][0][k-1]-prices[i-1] // 第i天 买入: 第i-1天没有股票，最大交易次数不能超过k-1
);

base case

dp[0][0][...] = 0; dp[0][1][...] = Integer.MIN_VALUE;
dp[...][0][0] = 0; dp[...][1][0] = Integer.MIN_VALUE;

二、打劫家舍问题

198.打劫家舍

213. 打家劫舍 II

337. 打家劫舍 III

1、打劫家舍

【状态】是 抢劫第i家时能获得的最大金额

// 状态转移方程
dp[i] = Math.max(dp[i-2], dp[i-3]) + nums[i];

2、打劫家舍Ⅱ

特别之处在于 nums 换成了环形数组

应对策略也十分巧妙

\(f([x_{1}, x_{2}, ... , x_{n}]) = max( f([x_{1}, x_{2}, ..., x_{n-1}]), f([x_{2}, ..., x_{n}]) )\)

既然首尾相连了，那么肯定最多只能抢劫一家，把另外一家除去，就把环形数组又变成了普通数组了。

3、打劫家舍Ⅲ

把家舍的形状变成了二叉树

class Solution {
    public int rob(TreeNode root) {
        int[] res = dp(root);
        return Math.max(res[0], res[1]);
    }

    // return {x, y} 
    // x: 包括root节点的最高金额 
    // y: 不包含root节点的最高金额
    private int[] dp(TreeNode root){
        if(root == null) return new int[]{0, 0};
        int[] left = dp(root.left);
        int[] right = dp(root.right);
        int x = left[1] + right[1] + root.val;
        int y = Math.max(left[1], left[0]) + Math.max(right[1], right[0]);
        return new int[]{x, y};
    }
}

三、博弈问题

486. 预测赢家

最核心最关键的还是在【找状态】，理解！！！

// 第一种比较容易理解的，三维数组
// dp[i][j][0] 表示在[xi...xj]区间时，先手的最大得分
dp[i][j][0] = Math.max(nums[i]+dp[i+1][j][1], nums[j]+dp[i][j-1][1]);
// [i...j] 先手可以选择i也可以选择j
// 选择i后，在[i+1...j]区间就变成了后手，就是dp[i+1][j][1]
// 选择j后，在[i...j+1]区间就变成了后手，就是dp[i][j-1][1]
if 先手选择了i: dp[i][j][1] = dp[i+1][j][0];
if 先手选择了j: dp[i][j][1] = dp[i][j-1][0];


// 第二种稍微改进一点，二维数组
// dp[i][j][1] 表示在[xi...xj]区间时，先手的最大得分-后手的最大得分
dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
// 在[i...j]先手做出选择后，就变成了后手，所以是<减>

四、扔鸡蛋（***）

887.鸡蛋掉落

这道题理解上难度很高...

image-20221104212852347

这里讲一个逆向思维。

dp[i][j] 表示有j个鸡蛋，可以操作i次，可以在最高dp[i][j]的建筑里保证找到f

比如dp[2][1]=2，表示有1个鸡蛋，可以操作2次，可以在最高2楼的建筑里保证找到f。意思就是如果楼>=3，就不能保证在1个鸡蛋2次操作的情况下找到f。这里的保证是指不管在什么情况下都可以成功找到f，而不是说有一定概率可以找到。很好理解，不管多高的楼层，即使给1个鸡蛋1次操作，也有一定概率可以找到f（第1层就碎了，所以f=0）

理解完状态之后，就需要找到状态转移方程。先给出来

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

这里应该是这道题最难理解的地方。