算法奇妙屋(十四)-简单多状态dp问题(动态规划)
算法奇妙屋(十四)-简单多状态dp问题(动态规划)
景画
发布于 2025-12-19 13:33:04
发布于 2025-12-19 13:33:04
一. 力扣面试题 17.16. 按摩师
1. 题目
这里题目的意思是这一组数据, 不能选择相邻的数字, 最少间隔一个, 然后求选择数据和的最大值
2. 算法原理
3. 代码
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]);
}二. 力扣LCR 090. 打家劫舍 II
1. 题目
相比于打家劫舍I(上一道题和打家劫舍I解法一样), 这里的房子只是变为了环形
在这里插入图片描述
2. 算法原理
在这里插入图片描述
3. 代码
public int rob(int[] nums) {
int n = nums.length;
// 0 偷
int t1 = robI(nums, 2, n - 2) + nums[0];
// 0 不偷
int t2 = robI(nums, 1, n - 1);
return Math.max(t1, t2);
}
public int robI(int[] nums, int start, int end) {
if (start > end) {
return 0;
}
int n = nums.length;
int[] f = new int[n];
int[] g = new int[n];
f[start] = nums[start];
for (int i = start + 1; i <= end; i++) {
f[i] = g[i - 1] + nums[i];
g[i] = Math.max(f[i - 1], g[i - 1]);
}
return Math.max(f[end], g[end]);
}三. 力扣740. 删除并获得点数
1. 题目
在这里插入图片描述
2. 算法原理
在这里插入图片描述
3. 代码
public int deleteAndEarn(int[] nums) {
int[] rob = new int[10001];
int max = 0;
for (int x : nums) {
if (x > max) {
max = x;
}
rob[x] += x;
}
int[] f = new int[max + 1];
int[] g = new int[max + 1];
f[0] = rob[0];
for (int i = 1; i <= max; i++) {
f[i] = g[i - 1] + rob[i];
g[i] = Math.max(f[i - 1], g[i - 1]);
}
return Math.max(f[max], g[max]);
} 四. 力扣LCR 091. 粉刷房子
1. 题目
在这里插入图片描述
2. 算法原理
在这里插入图片描述
3. 代码
public int minCost(int[][] costs) {
int n = costs.length;
int[] r = new int[n + 1];
int[] b = new int[n + 1];
int[] g = new int[n + 1];
for (int i = 1; i <= n; i++) {
r[i] = Math.min(b[i - 1], g[i - 1]) + costs[i - 1][0];
b[i] = Math.min(r[i - 1], g[i - 1]) + costs[i - 1][1];
g[i] = Math.min(b[i - 1], r[i - 1]) + costs[i - 1][2];
}
return Math.min(r[n],Math.min(b[n], g[n]));
}五. 力扣309. 买卖股票的最佳时机含冷冻期
1. 题目
在这里插入图片描述
2. 算法原理
小编参悟这道题也是参悟了2个小时,才弄懂, 只能第一次见到题解的时候云里雾里, 后来多想了想, 才弄明白一些隐含条件, 一些注意事项都写到了下面图解里
在这里插入图片描述
3. 代码
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]);
}六. 力扣714. 买卖股票的最佳时机含手续费
1. 题目
在这里插入图片描述
2. 算法原理
在这里插入图片描述
3. 代码
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int[] f = new int[n];
int[] g = new int[n];
f[0] = -prices[0];
for (int i = 1; i < n; i++) {
f[i] = Math.max(f[i - 1], g[i - 1] - prices[i]);
g[i] = Math.max(f[i - 1] + prices[i] - fee, g[i - 1]);
}
return g[n - 1];
}七. 力扣123. 买卖股票的最佳时机 III
1. 题目
在这里插入图片描述
2. 算法原理
在这里插入图片描述
3. 代码
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] f = new int[n][3];
int[][] g = new int[n][3];
f[0][0] = -prices[0];
f[0][1] = f[0][2] = g[0][1] = g[0][2] = -0x3f3f3f3f;
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]);
}
}
}
return Math.max(g[n - 1][0], Math.max(g[n - 1][1], g[n - 1][2]));
}八. 力扣188. 买卖股票的最佳时机 IV
1. 题目
相较于上一道题,这里的最大交易两次变为了k次, 但是丝毫不慌, 因为我们上一道题提供的解法是通用的, 不管你最大限制交易多少次, 都是一样的解法
在这里插入图片描述
2. 算法原理
因为我们上一道题的解法和这道题一模一样, 这里我就懒一下,不过多赘述, 直接从上面讲解法复制下来了, 同样也是方便大家观看
在这里插入图片描述
3. 代码
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] = -0x3f3f3f3f;
}
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]);
if (j - 1 >= 0) {
g[i][j] = Math.max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
}else {
g[i][j] = g[i - 1][j];
}
}
}
int max = 0;
for (int j = 0; j <= k; j++) {
if (g[n - 1][j] > max) {
max = g[n - 1][j];
}
}
return max;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-12-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
