网站建设整体流程,优化网站除了百度站长,网站后台怎么挂广告 怎么做,沈阳网站制作联系方式目录 123.买卖股票的最佳时机III188.买卖股票的最佳时机IV 123.买卖股票的最佳时机III
123题目链接 根据题意#xff1a;最多可以完成 两笔 交易#xff0c;即可以买卖股票一次#xff0c;可以买卖两次#xff0c;也可以不买卖
dp数组定义#xff1a;
此时 一天就有五个… 目录 123.买卖股票的最佳时机III188.买卖股票的最佳时机IV 123.买卖股票的最佳时机III
123题目链接 根据题意最多可以完成 两笔 交易即可以买卖股票一次可以买卖两次也可以不买卖
dp数组定义
此时 一天就有五个状态
没有操作第一次持有股票第一次不持有股票第二次持有股票第二次不持有股票
dp[i] [j]中 i 表示第 i 天j 为 [0 - 4] 五个状态dp[i] [j]表示第 i 天状态 j 所剩最大现金。
递推公式
达到dp[i] [1]状态(第一次持有股票)有两个具体操作
1第 i 天买入股票 dp[i] [1] dp[i - 1] [0] - prices[i];
2第 i 天 没有操作dp[i] [1] dp[i - 1] [1];
选择两者 之间最大的 dp[i] [1] max (dp[i - 1] [0] - prices[i], dp[i - 1] [1]);
达到dp[i] [2] 状态(第一次不持有股票)也有两个操作
1第 i 天卖出股票 dp[i] [2] dp[i - 1] [1] prices[i];
2第 i 天 没有操作dp[i] [2] dp[i - 1] [2];
选择两者 之间最大的dp[i] [2] max (dp[i - 1] [1] prices[i], dp[i - 1] [2])
达到dp[i] [3]状态(第二次持有股票)同样为两个操作
1第 i 天 买入第二次买入股票 dp[i] [3] dp[i - 1] [2] - prices[i];
2第 i 天 没有操作 dp[i] [3] dp[i - 1] [3];
dp[i] [3] max(dp[i - 1] [2] - prices[i], dp[i - 1] [3]);
达到 dp[i] [4]状态(第二次不持有股票) 同样为两个操作
1第 i 天 卖出 第二次买入的股票dp[i] [4] dp[i - 1] [3] prices[i];
2第 i 天 没有操作dp[i] [4] dp[i - 1] [4];
dp[i] [4] max(dp[i - 1] [3] prices[i], dp[i - 1] [4])
dp 数组初始化
对 第 0 天的五个状态进行初始化
dp[0] [0] 0;
dp[0] [1] -prices[i];
dp[0] [2] 0; 买入完 立即卖出
dp[0] [3] -prices[i];
dp[0] [4] 0;
遍历顺序 从前往后
注意
获取的最大利润一定是 在卖完第二次持有的股票时
就是有可能 第一次卖出的已经是最大值此时 可以在当天立刻买入后再立刻卖出也就是卖完第二次持有的股票这种情况包含了 卖完第一次持有股票这种情况。
class Solution {
public:int maxProfit(vectorint prices) {vectorvectorint dp(prices.size(), vectorint(5));dp[0][0] 0;dp[0][1] -prices[0];dp[0][2] 0;dp[0][3] -prices[0];dp[0][4] 0;for (int i 1; i prices.size(); i) {dp[i][0] dp[i - 1][0];dp[i][1] max(dp[i - 1][0] - prices[i], dp[i - 1][1]);dp[i][2] max(dp[i - 1][1] prices[i], dp[i - 1][2]);dp[i][3] max(dp[i - 1][2] - prices[i], dp[i - 1][3]);dp[i][4] max(dp[i - 1][3] prices[i], dp[i - 1][4]);}return dp[prices.size() - 1][4];}
};188.买卖股票的最佳时机IV
188题目链接 该题 相当于是 对 123. 买卖股票的最佳时机 III题目的推广从 题123 中 找出规律整体思路与 题123 一致。
class Solution {
public:int maxProfit(int k, vectorint prices) {vectorvectorint dp(prices.size(), vectorint(2 * k 1));for (int i 0; i 2 * k; i i 2) {dp[0][i] 0;}for (int i 1; i 2 * k; i i 2) {dp[0][i] -prices[0];}for (int i 1; i prices.size(); i) {dp[i][0] dp[i - 1][0];for (int j 1; j 2 * k; j) {if (j % 2 0) {dp[i][j] max (dp[i - 1][j - 1] prices[i], dp[i - 1][j]);}else {dp[i][j] max (dp[i - 1][j - 1] - prices[i], dp[i - 1][j]);}}}return dp[prices.size() - 1][2 * k];}
};
