用自己的身份做网站备案,阿里云 xampp wordpress,网站做导航的地图导航,cname wordpress【问题描述】[中等] 【解答思路】
1. 动态规划
动态规划流程 第 1 步#xff1a;设计状态 f[i]表示第 i 天结束之后的「累计最大收益」 第 2 步#xff1a;状态转移方程
f[i][0]max(f[i−1][0],f[i−1][2]−prices[i]) f[i][1]f[i−1][0]prices[i] f[i][2]max(f[i−1][1]…【问题描述】[中等] 【解答思路】
1. 动态规划
动态规划流程 第 1 步设计状态 f[i]表示第 i 天结束之后的「累计最大收益」 第 2 步状态转移方程
f[i][0]max(f[i−1][0],f[i−1][2]−prices[i]) f[i][1]f[i−1][0]prices[i] f[i][2]max(f[i−1][1],f[i−1][2])
第 3 步考虑初始化 第 4 步考虑输出 max(f[n−1][0],f[n−1][1],f[n−1][2]) ➡ max(f[n−1][1],f[n−1][2])
第 5 步考虑是否可以状态压缩 可 见方法2 f[0][1] 置为0 因为f[1][1]只和f[0][0]有关系f[0][1]只影响f[1][2],而f[1][2]又是由f[0][1]和f[0][2]共同决定的第0天f[0][1]和f[0][2]是同一状态也就无所谓了。 时间复杂度O(N) 空间复杂度O(N)
class Solution {public int maxProfit(int[] prices) {if (prices.length 0) {return 0;}int n prices.length;// f[i][0]: 手上持有股票的最大收益// f[i][1]: 手上不持有股票并且处于冷冻期中的累计最大收益// f[i][2]: 手上不持有股票并且不在冷冻期中的累计最大收益int[][] f new int[n][3];f[0][0] -prices[0];for (int i 1; i n; i) {f[i][0] Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);f[i][1] f[i - 1][0] prices[i];f[i][2] Math.max(f[i - 1][1], f[i - 1][2]);}return Math.max(f[n - 1][1], f[n - 1][2]);}
}
2. 动态规划路径压缩 时间复杂度O(N) 空间复杂度O(1)
class Solution {public int maxProfit(int[] prices) {if (prices.length 0) {return 0;}int n prices.length;int f0 -prices[0];int f1 0;int f2 0;for (int i 1; i n; i) {int newf0 Math.max(f0, f2 - prices[i]);int newf1 f0 prices[i];int newf2 Math.max(f1, f2);f0 newf0;f1 newf1;f2 newf2;}return Math.max(f1, f2);}
}
【总结】
1.动态规划流程
第 1 步设计状态 第 2 步状态转移方程 第 3 步考虑初始化 第 4 步考虑输出 第 5 步考虑是否可以状态压缩
2. 三个状态 三数组DP 两数组DP信息量过大 处理不来
转载链接https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/zui-jia-mai-mai-gu-piao-shi-ji-han-leng-dong-qi-4/
