蓝色系网站设计,网站论坛怎么建设,北京网站制作的流程,通信管理局网站 备案文章目录 动态规划理论基础动规五部曲#xff1a;出现结果不正确#xff1a; 1. 最佳买卖股票的时机含冷冻期2. 买卖股票的最佳时机含手续费 动态规划理论基础
动规五部曲#xff1a;
确定dp数组 下标及dp[i] 的含义。递推公式#xff1a;比如斐波那契数列 dp[i] dp[i-1… 文章目录 动态规划理论基础动规五部曲出现结果不正确 1. 最佳买卖股票的时机含冷冻期2. 买卖股票的最佳时机含手续费 动态规划理论基础
动规五部曲
确定dp数组 下标及dp[i] 的含义。递推公式比如斐波那契数列 dp[i] dp[i-1] dp[i-2]。初始化dp数组。确定遍历顺序从前到后or其他。打印。
出现结果不正确
打印dp日志和自己想的一样递推公式、初始化或者遍历顺序出错。打印dp日志和自己想的不一样代码实现细节出现问题。
1. 最佳买卖股票的时机含冷冻期 参考文档代码随想录 分析 加入冷冻期的概念如果当前卖出了会有一天的冷冻期这一天不能买入股票所以节点的状态增加为 持有 当场卖出 冷冻期 和 卖出状态 四种。卖出状态是说明可以持有股票了。 递推公式
dp[i][0] max(dp[i-1][0], max(dp[i-1][2]-prices[i], dp[i-1][3]-prices[i]));
dp[i][1] dp[i-1][0] prices[i];
dp[i][2] dp[i-1][1];
dp[i][3] max(dp[i-1][3], dp[i-1][2]);代码
class Solution {
public:int maxProfit(vectorint prices) {//比较重要的是状态的细分vectorvectorint dp(prices.size(), vectorint(4, 0));dp[0][0] -prices[0];//持有dp[0][1] 0;//当天卖出dp[0][2] 0;//冷冻期dp[0][3] 0;//卖出状态for(int i 1; i prices.size(); i){dp[i][0] max(dp[i-1][0], max(dp[i-1][2]-prices[i], dp[i-1][3]-prices[i]));dp[i][1] dp[i-1][0] prices[i];dp[i][2] dp[i-1][1];dp[i][3] max(dp[i-1][3], dp[i-1][2]);}return max(max(dp[prices.size()-1][0],dp[prices.size()-1][1]),max(dp[prices.size()-1][2], dp[prices.size()-1][3]));}
};2. 买卖股票的最佳时机含手续费 参考文档代码随想录 分析 手续费什么是否付呢需要卖出的时候就要付了。每个节点的状态有两个持有和不持有手里的钱。 递推公式
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(vectorint prices, int fee) {vectorvectorint dp(prices.size(), vectorint(2,0));dp[0][0] -prices[0];dp[0][1] 0;for(int i 1; i prices.size(); 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][0] prices[i] - fee);}return max(0,max(dp[prices.size()-1][1], dp[prices.size()-1][0]));}
};
