旅游网站建设策划方案书,wordpress附件下载失败,为什么做网站推广,网站建设计无形资产#x1f308;#x1f308;#x1f604;#x1f604;
欢迎来到茶色岛独家岛屿#xff0c;本期将为大家揭晓动态规划之买卖股票问题 #xff0c;做好准备了么#xff0c;那么开始吧。
#x1f332;#x1f332;#x1f434;#x1f434; 动态规划算法本质上就是穷举…
欢迎来到茶色岛独家岛屿本期将为大家揭晓动态规划之买卖股票问题 做好准备了么那么开始吧。 动态规划算法本质上就是穷举「状态」然后在「选择」中选择最优解。这个问题的「状态」有三个第一个是天数第二个是允许交易的最大次数第三个是当前的持有状态即之前说的 rest 的状态我们不妨用 1 表示持有0 表示没有持有。然后我们用一个三维数组就可以装下这几种状态的全部组合比如说 dp[3][2][1] 的含义就是今天是第三天我现在手上持有着股票至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义今天是第二天我现在手上没有持有股票至今最多进行 3 次交易。时刻牢记「状态」的定义状态 k 的定义并不是「已进行的交易次数」而是「最大交易次数的上限限制」。如果确定今天进行一次交易且要保证截至今天最大交易次数上限为 k那么昨天的最大交易次数上限必须是 k - 1。 状态转移方程
base case
dp[-1][...][0] dp[...][0][0] 0
dp[-1][...][1] dp[...][0][1] -infinity状态转移方程
dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i])
dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
121. 买卖股票的最佳时机
一、力扣示例
121. 买卖股票的最佳时机 - 力扣LeetCodehttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
二、解决办法
现在发现 k 都是 1不会改变即 k 对状态转移已经没有影响了。
可以进行进一步化简去掉所有 k
dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i])
dp[i][1] max(dp[i-1][1], -prices[i])
三、代码实现
class Solution {public int maxProfit(int[] prices) {int n prices.length;int[][] dp new int[n][2];for (int i 0; i n; i) {if (i - 1 -1) {// base casedp[i][0] 0;dp[i][1] -prices[i];continue;}dp[i][0] Math.max(dp[i-1][0], dp[i-1][1] prices[i]);dp[i][1] Math.max(dp[i-1][1], -prices[i]);}return dp[n - 1][0];}
} 122. 买卖股票的最佳时机 II
一、力扣示例
122. 买卖股票的最佳时机 II - 力扣LeetCodehttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
二、解决办法
我们发现数组中的 k 已经不会改变了也就是说不需要记录 k 这个状态了
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])
三、代码实现
class Solution {public int maxProfit(int[] prices) {int nprices.length;int dp[][]new int[n][2];dp[0][0]0;dp[0][1]-prices[0];for(int i1;in;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]);}return dp[n-1][0];}
} 309. 最佳买卖股票时机含冷冻期
一、力扣示例
309. 最佳买卖股票时机含冷冻期 - 力扣LeetCodehttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
二、解决办法
dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i])
dp[i][1] max(dp[i-1][1], dp[i-2][0] - prices[i])
解释第 i 天选择 buy 的时候要从 i-2 的状态转移而不是 i-1 。 三、代码实现
class Solution {public int maxProfit(int[] prices) {int nprices.length;int dp[][]new int[n][2];dp[0][0] 0;dp[0][1] -prices[0];for(int i1;in;i){if (i - 2 -1) {// base case 2dp[i][0] Math.max(dp[i-1][0], dp[i-1][1] prices[i]);dp[i][1] Math.max(dp[i-1][1], -prices[i]);continue;}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-2][0]-prices[i]);}return dp[n-1][0];}
} 714. 买卖股票的最佳时机含手续费
一、力扣示例
714. 买卖股票的最佳时机含手续费 - 力扣LeetCodehttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
二、解决办法
每次交易要支付手续费只要把手续费从利润中减去即可改写方程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)
解释相当于买入股票的价格升高了。
在第一个式子里减也是一样的相当于卖出股票的价格减小了。
三、代码实现
class Solution {public int maxProfit(int[] prices, int fee) {int n prices.length;int[][] dp new int[n][2];for (int i 0; i n; i) {if (i - 1 -1) {// base casedp[i][0] 0;dp[i][1] -prices[i] - fee;continue;}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][0];}
} 123. 买卖股票的最佳时机 III
一、力扣示例
123. 买卖股票的最佳时机 III - 力扣LeetCodehttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
二、解决办法 原始的状态转移方程没有可化简的地方
dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i])
dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
三、代码实现
class Solution {public int maxProfit(int[] prices) {int max_k 2, n prices.length;int[][][] dp new int[n][max_k 1][2];for (int i 0; i n; i) {for (int k 1; k max_k; k) {if (i - 1 -1) {// 处理 base casedp[i][k][0] 0;dp[i][k][1] -prices[i];continue;}dp[i][k][0] Math.max(dp[i-1][k][0], dp[i-1][k][1] prices[i]);dp[i][k][1] Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);}}// 穷举了 n × max_k × 2 个状态正确。return dp[n - 1][max_k][0];}} 188. 买卖股票的最佳时机 IV
一、力扣示例
188. 买卖股票的最佳时机 IV - 力扣LeetCodehttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
二、解决办法 有了上一题 k 2 的铺垫这题应该和上一题的第一个解法没啥区别你把上一题的 k 2 换成题目输入的 k 就行了。 但试一下发现会出一个内存超限的错误原来是传入的 k 值会非常大dp 数组太大了。那么现在想想交易次数 k 最多有多大呢 一次交易由买入和卖出构成至少需要两天。所以说有效的限制 k 应该不超过 n/2如果超过就没有约束作用了相当于 k 没有限制的情况而这种情况是之前解决过的。 三、代码实现
class Solution {public int maxProfit(int max_k, int[] prices) {int n prices.length;if (n 0) {return 0;}if (max_k n / 2) {// 复用之前交易次数 k 没有限制的情况return maxProfit_k_inf(prices);}int[][][] dp new int[n][max_k 1][2];// k 0 时的 base casefor (int i 0; i n; i) {dp[i][0][1] Integer.MIN_VALUE;dp[i][0][0] 0;}for (int i 0; i n; i) for (int k max_k; k 1; k--) {if (i - 1 -1) {// 处理 i -1 时的 base casedp[i][k][0] 0;dp[i][k][1] -prices[i];continue;}dp[i][k][0] Math.max(dp[i-1][k][0], dp[i-1][k][1] prices[i]);dp[i][k][1] Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]); }return dp[n - 1][max_k][0];}public int maxProfit_k_inf(int[] prices) {int n prices.length;int[][] dp new int[n][2];for (int i 0; i n; i) {if (i - 1 -1) {// base casedp[i][0] 0;dp[i][1] -prices[i];continue;}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]);}return dp[n - 1][0];}
}
