算法【Java】—— 动态规划之简单多状态 dp 问题 算法【Java】—— 动态规划之简单多状态 dp 问题
按摩师
https://leetcode.cn/problems/the-masseuse-lcci
状态表示:根据经验和题目要求,达到 i 位置的时候,预约时间最长
接着我们细分状态表示:在遍历数组的时候,到达 i 位置的时候,又两种情况,要么接收预约,要么不接受预约。这里有两种状态,可以使用一个二维 dp 表,这里使用两个 dp 表,一个是 f[i] 说明接受预约,g[i] 说明不接受预约。
状态转移方程推导:f[i] 说明在 i 位置接受了预约,那么 i - 1 就不能接受预约,因为按摩师不接受相邻的位置的预约。那么在 i 位置最大预约时间应该等于 i - 1 位置最大预约时长加上 nums[i] 位置 即 f[i] = g[i-1] + nums[i]
g[i] 说明 i 位置不接受预约,那么 i - 1 位置就有两种情况,要么接受预约,要么不接受预约,我们取者两种情况的最大值。g[i] = max(f[i-1], g[i-1]);
初始化:由于用到了前一个的节点,为了避免填表的越界访问,所以将第一个节点初始化一下(f[0] = nums[0], g[0] = 0;),然后从第二个节点开始填表
填表顺序:从左到右,两个表同时填
返回两个表最后一个节点的最大值
class Solution {
public int massage(int[] nums) {
int n = nums.length;
if(n == 0) return 0;
int[] f = new int[n];
int[] g = new int[n];
f[0] = nums[0];
for(int i = 1; i < n; i++) {
f[i] = g[i-1] + nums[i];
g[i] = Math.max(g[i-1], f[i-1]);
}
return Math.max(f[n-1], g[n-1]);
}
}
打家劫舍Ⅱ
https://leetcode.cn/problems/house-robber-ii
解析:
这里就是首尾不能同时偷,除去首位两个位置,其他位置本质上和我们上一题的按摩师是一样的。
我们可以封装一个方法,该方法放多两个参数,也就是起始位置和终止位置,在此范围进行打家劫舍。
进行分类讨论,当偷了第一个节点的时候,我们只能从第三个节点到倒数第二个节点之间进行偷取,如果不偷第一个节点,我们可以从第二个节点到最后一个节点进行偷取。
class Solution {
public int rob(int[] nums) {
int n = nums.length;
return Math.max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n-1));
}
int rob1(int[] nums, int left, int right) {
if(left > right) {
return 0;
}
int n = nums.length;
int[] f = new int[n];
int[] g = new int[n];
f[left] = nums[left];
for(int i = left + 1; i
删除并获得点数
https://leetcode.cn/problems/delete-and-earn
解析:
我们可以先对数组排个序,或者使用数组来模拟哈希表来存储数据方便我们进行删除操作。无论是哪种形式,最后数据一定是有序的,接着就是我们的动态规划了。
题目说如果删除了 nums[i], 就要连通 nums[i] +1 和 nums[i] - 1 一起删除,和上面的打家劫舍很相似,也就是我偷了这个位置的数值之后,相邻两边的数值是不能在偷了。
状态表示:当达到 i 位置的时候,要么删除获得当前最大点数,要么不删除获得当前最大点数,使用两个 dp 表来存储状态值。f[i] 表示删除 i 位置获得最大点数,g[i] 表示不删除 i 位置获得最大点数。
状态转移方程:f[i] = g[i-1] + i 位置的点数
g[i] = max(f[i-1], g[i-1])
初始化,由于要用到前一个节点,为了避免填表的越界访问,所以将第一个节点初始化一下。初始化 f[0 = arr[0] * 0 = 0, g[0] = 0
填表顺序:从左到右,两表同时填写
返回两个表最后一个节点的最大值
参考代码:
class Solution {
public int deleteAndEarn(int[] nums) {
int n = 10001;
int[] arr = new int[n];
for(int x : nums) {
arr[x]++;
}
int[] f = new int[n];
int[] g = new int[n];
for(int i = 1; i < n; i++) {
f[i] = g[i-1] + arr[i] * i;
g[i] = Math.max(f[i-1], g[i-1]);
}
return Math.max(f[n-1], g[n-1]);
}
}
粉刷房子
https://leetcode.cn/problems/JEj789
解析:
状态表示:还是和之前的思路一样,到达 i 位置 的时候,当前的粉刷费用最低。
还可以细分,达到 i 位置有三种刷法,红色,蓝色,绿色。那就是三个 dp 表,我们可以建一个二维的 dp 表即 dp[n][3],dp[i][0] 表示 i 位置刷成红色时费用最低,dp[i][1] 表示 i 位置刷成蓝色费用最低,dp[i][2] 表示 i 位置刷成绿色费用最低。
状态转移方程:由于相邻两个位置不能颜色相同,所以 dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + 对应的 i 位置的红色费用,dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + 对应的 i 位置的蓝色费用,dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + 对应的 i 位置的绿色费用
初始化,因为要用到前一个节点的数值,为了避免填表的越界访问,所以将第一个节点初始化一下。dp[0][0] = costs[0][0],dp[0][1] = costs[0][1],dp[0][2] = costs[0][2]
填表顺序:从左到右,两表同时填
返回值,遍历 dp 表最后一行返回最小值。
class Solution {
public int minCost(int[][] costs) {
int n = costs.length;
int[][] dp = new int[n][3];
dp[0][0] = costs[0][0];
dp[0][1] = costs[0][1];
dp[0][2] = costs[0][2];
for(int i = 1; i < n; i++) {
dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + costs[i][0];
dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + costs[i][1];
dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + costs[i][2];
}
int ret = Integer.MAX_VALUE;
for(int i = 0; i < 3; i++) {
ret = Math.min(ret, dp[n-1][i]);
}
return ret;
}
}
买卖股票的最佳时期
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown
解析:
状态表示:第 i 天结束的时候,获得最大利润。
细分状态表示:第 i 天结束的时候要么持有股票,要么没有股票,持有股票处于 “买入” 状态,没有股票要么处于冷静期(此时不能购买股票),要么处于 "可交易” 状态(可以买股票),那么一共有三种状态,我们使用一个二维的 dp 表 dp[n][3] ,dp[i][0] 表示 “买入”状态,dp[i][1] 表示 ”冷静期“ 状态,dp[i][2] 表示 ”卖出“ 状态。
当状态比较复杂的时候,我们可以画个图:
解释一下箭头的含义,箭头的起始位置表示第 i 天的开始,然后箭头的 身体表示 第 i 天做了什么操作,箭头最后指向的就是第 i 天结束的时候达到的状态。
这个图还有个名字叫做 “状态机”,根据图我们可以很容易地写出状态转移方程:
dp[i][0] = max(dp[i-1][0],dp[i-1][2] - prices[i])
dp[i][1] = dp[i-1][0] + prices[i]
dp[i][2] = max(dp[i-1][1], dp[i-1][2])
初始化,由于要用到前一行的状态值,所以要初始化第一行,避免后面填表的越界访问。
填表顺序:从上到下,从左到右,三表同时填。
返回值:返回 dp 表最后一个的最大利润值,还可以再简化一下,返回 Math.max(dp[i][1], dp[i][2]),因为最后一天还持有股票的话,是不可能达到利润的最大值。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][3];
dp[0][0] = -prices[0];
for(int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2] - prices[i]);
dp[i][1] = dp[i-1][0] + prices[i];
dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]);
}
return Math.max(dp[n-1][1], dp[n-1][2]);
}
}
买卖股票的最佳时期含手续费
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
解析:
这里有个手续费的操作,我们设置每次把股票卖出去的时候算作一次交易,也就是在卖出股票的时候才扣除手续费 fee
状态表示:第 i 天结束的时候,利润最大。
继续细分状态,第 i 天结束的时候,要么持有股票(设为“买入”状态),要么没有股票(设为“卖出”状态),使用 二维 dp 表 dp[n][2] 来表示, dp[i][0] 表示 “买入”状态,dp[i][1] 表示 “卖出” 状态。
当状态多的时候,我们可以画个图:
状态转移方程:
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
初始化第一行:dp[0][0] = -prices[0]; dp[0][1] = 0;
填表顺序:从上到下,从左到右
返回dp[n-1][1]
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][0] = -prices[0];
for(int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
}
return dp[n-1][1];
}
}
买卖股票的最佳时机 Ⅲ
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii
解析:
状态表示:第 i 天结束的时候,获得最大利润
接着细分状态表示,第 i 天结束的时候,要么持有股票,要么不持有股票,并且由于题目有要求最多进行两笔交易,我们这里定义卖出股票的时候算作一笔交易,那么还要有一个状态就是这是 第 几笔交易
那么我们重新定义状态:第 i 天结束的时候,持有股票(处于“买入”状态),这是第 j 笔交易,并且利润最大,使用 f[i][j] 二维 dp 表表示
第 i 天结束的时候,没有股票(处于“卖出”状态),这是第 j 笔交易,并且利润最大,使用 g[i][j] 二维 dp 表表示
画个状态机:
状态转移方程:
f[i][j] = max(f[i-1][j],g[i-1][j] - prices[i])
g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i])
初始化:
上面两个状态转移方程都需要用到前一行的状态值,所以将第一行初始化一下,首先 f 表来,f 表表示 “买入” 状态,要想买入,就必须买下第 0 天的股票 即 f[0][0] = -prices[i],f[0] 这一行的其他列是没有数值的,因为第 0 天的交易笔数是 0,所以剩下的空位必须保证不能影响到第二行的填表,此时应该设置为 无穷小
接着就是 g 表,表示 “卖出状态”,第 0 天 第 0 笔交易没有股票卖出,只能 为 0,即 g[0][0] = 0,第 0 行 剩余的其他空位要不影响到 g 表下一行的填写,所以应该设置为 无穷小。
注意:无穷小不能直接定义为 Integer.MIN_VALUE,因为 f[i][j] = max(f[i-1][j],g[i-1][j] - prices[i])
其中的 g[i-1][j] - prices[i]
这个式子,如果为 Integer.MIN_VALUE 的话,一减会发生溢出现象或者运行报错,所以这里的无穷小,一般我们设置为 0x3f3f3f
细节处理:因为g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i])
中要用到 f[i-1][j-1], 这可能会发生越界,所以我们填表的时候可以加一个 判断条件 if(j-1 >= 0)
才进行 max 的比较,如果 j - 1 小于 0 ,说明对应的 f 状态值不存在,直接将 g[i-1][j] 赋值给 g[i][j]
i 表示天数,所以直接是 prices.length 行,那多少列合适呢?题目告诉我们最多有两笔交易,所以应该是 3 列(0 笔交易,1 笔交易,2 笔交易),所以 f 表和 g 表应该为 n 行 3 列
填表顺序:从上到下,从左到右,双表一起填
返回值,遍历 g 表最后一行,返回最大值
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] f = new int[n][3];
int[][] g = new int[n][3];
for(int i = 1; i < 3; i++) {
f[0][i] = g[0][i] = -0x3f3f3f;
}
f[0][0] = -prices[0];
for(int i = 1; i < n; i++) {
for(int j = 0; j < 3; j++) {
f[i][j] = Math.max(f[i-1][j], g[i-1][j] - prices[i]);
g[i][j] = g[i-1][j];
if(j - 1 >= 0) {
g[i][j] = Math.max(g[i][j], f[i-1][j-1] + prices[i]);
}
}
}
int ret = 0;
for(int i = 0; i < 3; i++) {
ret = Math.max(ret, g[n-1][i]);
}
return ret;
}
}
买卖股票的最佳时机 Ⅳ
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv
解析和上面一题是一样的,这里不赘述了,交给大家练手了。
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
int[][] f = new int[n][k+1];
int[][] g = new int[n][k+1];
for(int j = 1; j