做网站用广告赚钱过时了,青峰集团响应式网站,关于江西建设监督网网站迁移,网站移动端和手机端分开做目录
动态规划怎么学#xff1f;
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后#xff1a; 动态规划怎么学#xff1f;
学习一个算法没有捷径#xff0c;更何况是学习动态规划#xff0c;
跟我…目录
动态规划怎么学
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后 动态规划怎么学
学习一个算法没有捷径更何况是学习动态规划
跟我一起刷动态规划算法题一起学会动态规划
1. 题目解析
题目链接309. 最佳买卖股票时机含冷冻期 - 力扣Leetcode 这道题很好理解其实就是买股票的时候多了一个冷冻期。
2. 算法原理
1. 状态表示
因为他有三种情况所以我们也有三种状态表示
dp[ i ][ 0 ] 表示第 i 天是 “买入” 状态此时的最大利润。
dp[ i ][ 1 ] 表示第 i 天是 “可卖出” 状态此时的最大利润。
dp[ i ][ 2 ] 表示第 i 天是 “冷冻” 状态此时的最大利润。
2. 状态转移方程
我们一个一个分析状态表示
首先是买入状态怎么样让第 i 天进入买入状态
如果 i - 1 天结束是买入状态买过股票那就已经是买入状态
如果 i - 1 天结束是可交易状态可以卖股票但没买那只要这天买入就可以进入买入状态
如果 i - 1 天结束是冷冻状态就是卖出的后一天这样就不能进入买入状态。
然后是冷冻状态怎么样让第 i 天进入冷冻状态
如果 i - 1 天结束是买入状态那只要这天卖出就能进入冷冻状态
如果 i - 1 天结束是可交易状态那只要这天卖了也能进入冷冻状态
如果 i - 1 天结束是冷冻状态那第 i 天结束不可能是冷冻状态因为没东西可以卖了。
然后是可交易状态怎么样让第 i 天进入可交易状态
如果 i - 1 天结束是买入状态那就不是可交易状态而是买入状态。
如果 i - 1 天结束是可交易状态那也只需要啥都不干就是可交易状态
如果 i - 1 天结束是冷冻状态那也只需要啥都不干就是可交易状态。
所以我们根据上面的分析来写状态转移方程
dp[ i ][ 0 ] max( dp[ i - 1 ][ 0 ]dp[ i - 1 ][ 1 ] - p[ i ] )
dp[ i ][ 1 ] max( dp[ i - 1 ][ 1 ]dp[ i - 1 ][ 2 ] )
dp[ i ][ 2 ] dp[ i - 1 ][ 0 ] p[ i ]
3. 初始化
我们只需要把 dp[ 0 ][ 0 ] 初始化成 -p[ 0 ] 即可因为买入了所以最大利润就是一个负值。
4. 填表顺序
从左往右依次填写三个表即可。
5. 返回值
其实就是max( dp[ n - 1 ][ 1 ]dp[ n - 1 ][ 2 ] )
第一种买入的情况不考虑因为都买入了肯定不会是最大利润。
3. 代码编写
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();vectorvectorint dp(n, vectorint(3));dp[0][0] -prices[0];for(int i 1; i n; i) {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][2]);dp[i][2] dp[i - 1][0] prices[i];}return max(dp[n - 1][1], dp[n - 1][2]);}
};
写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
