做的网站缩小内容就全乱了,免费简约ppt模板,天津建设工程信息网报名,给女朋友做情侣网站的程序员目录 1.买卖股票的最佳时机含冷冻期1.题目链接买卖股票的最佳时机含冷冻期2.算法原理详解3.代码实现 2.买卖股票的最佳时机含手续费1.题目链接2.算法原理详解3.代码实现 1.买卖股票的最佳时机含冷冻期 1.题目链接
买卖股票的最佳时机含冷冻期
2.算法原理详解
思路#xff… 目录 1.买卖股票的最佳时机含冷冻期1.题目链接买卖股票的最佳时机含冷冻期2.算法原理详解3.代码实现 2.买卖股票的最佳时机含手续费1.题目链接2.算法原理详解3.代码实现 1.买卖股票的最佳时机含冷冻期 1.题目链接
买卖股票的最佳时机含冷冻期
2.算法原理详解
思路 确定状态表示 - dp[i][j]的含义i - 到了哪天j - 当天处于什么状态 dp[i][0]第i天结束之后处于买入状态此时的最大利润dp[i][1]第i天结束之后处于可交易状态此时的最大利润dp[i][2]第i天结束之后处于冷冻期状态此时的最大利润 推导状态转移方程本题关系复杂可以画图辅助 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] 初始化 dp[0][0] -p[0], dp[0][1] dp[0][2] 0 确定填表顺序从左往右一次填写三个表 确定返回值max(dp[n - 1][1], dp[n - 2][2]) 3.代码实现
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]);
}2.买卖股票的最佳时机含手续费
1.题目链接
买卖股票的最佳时机含手续费 2.算法原理详解
思路 确定状态表示 - dp[i]的含义 第i天结束之后所能获得的最大利润本题状态表示还可以继续细分 f[i]第i天结束之后处于“买入”状态此时的最大利润g[i]第i天结束之后处于“卖出”状态此时的最大利润 推导状态转移方程本题关系复杂可以画图辅助 f[i] max(f[i - 1], g[i - 1] - p[i])g[i] max(g[i - 1], f[i - 1] p[i] - fee) 初始化 f[0] -p[0], g[0] 0 确定填表顺序从左往右两个表一起填 确定返回值g[n - 1] 3.代码实现
int maxProfit(vectorint prices, int fee)
{int n prices.size();vectorint f(n); // 买入vectorint g(n); // 卖出f[0] -prices[0];for(int i 1; i n; i){f[i] max(f[i - 1], g[i - 1] - prices[i]);g[i] max(g[i - 1], f[i - 1] prices[i] - fee);}return g[n - 1];
}
