广西网站建设设计,山东兴润建设集团网站,施甸网站建设,网站建设具体工作总结文章目录 动态规划理论基础动规五部曲#xff1a;出现结果不正确#xff1a; 1. 买卖股票的最佳时机2. 买卖股票的最佳时机Ⅱ 动态规划理论基础
动规五部曲#xff1a;
确定dp数组 下标及dp[i] 的含义。递推公式#xff1a;比如斐波那契数列 dp[i] dp[i-1] dp[i-2]。初… 文章目录 动态规划理论基础动规五部曲出现结果不正确 1. 买卖股票的最佳时机2. 买卖股票的最佳时机Ⅱ 动态规划理论基础
动规五部曲
确定dp数组 下标及dp[i] 的含义。递推公式比如斐波那契数列 dp[i] dp[i-1] dp[i-2]。初始化dp数组。确定遍历顺序从前到后or其他。打印。
出现结果不正确
打印dp日志和自己想的一样递推公式、初始化或者遍历顺序出错。打印dp日志和自己想的不一样代码实现细节出现问题。
1. 买卖股票的最佳时机 参考文档代码随想录 分析 买卖只有一次 dp五部曲
dp[i]含义dp[i][0]表示持有i手里的现金dp[i][1]表示不持有i手里的现金。递推公式dp[i][0] max(dp[i-1][0], 0 - prices[i]); dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i]);初始化dp[0][0] -prices[0]; dp[0][1] 0;遍历顺序从小到大。
代码
class Solution {
public:int maxProfit(vectorint prices) {//dp[i][0]:持有i股手里的钱//dp[i][1]:不持有i股手里的钱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][0] max(dp[i-1][0], -prices[i]);dp[i][1] max(dp[i-1][1], dp[i-1][0]prices[i]);}return max(dp[prices.size()-1][0], dp[prices.size()-1][1]);}
};2. 买卖股票的最佳时机Ⅱ 参考文档代码随想录 分析 买卖次数是不限的之前有用贪心做过这次用动态规划。 dp五部曲
dp[i]含义dp[i][0]表示持有i手里的现金dp[i][1]表示不持有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]);初始化dp[0][0] -prices[0]; dp[0][1] 0;遍历顺序从小到大。
代码
class Solution {
public:int maxProfit(vectorint prices) {//dp[i][0]:i股持有手里的现金i-1股也持有i-1股不持有i股重新买入设计多次买入和一次手中只有一股股票//dp[i][1]:i股不持有手里的现金:i-1股也不持有现金不变i-1股持有i不持有卖出i-1买入i股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]);//i-1股持有i股不持有i股抛出收益prices[i] dp[i-1][0]prices[i]dp[i][1] max(dp[i-1][1], dp[i-1][0]prices[i]);}return max(dp[prices.size()-1][0], dp[prices.size()-1][1]);}
};
