算法【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 <= right; i++) {
f[i] = g[i-1] + nums[i];
g[i] = Math.max(g[i-1], f[i-1]);
}
return Math.max(g[right], f[right]);
}
}
删除并获得点数
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 <= k; j++) {
f[0][j] = g[0][j] = -0x3f3f3f;
}
f[0][0] = - prices[0];
for(int i = 1; i < n; i++) {
for(int j = 0; j <= k; 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 j = 0; j <= k; j++) {
ret = Math.max(ret, g[n-1][j]);
}
return ret;
}
}
原文地址：https://blog.csdn.net/liwuqianhzc/article/details/143820675
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！