当前位置：首页 > news >正文

代码随想录算法训练营 Day40 动态规划Ⅷ 股票问题

news 来源：原创 2025/8/13 11:41:16

动态规划

题目

121. 买卖股票的最佳时机 - 力扣（LeetCode）
使用二维 dp 数组表示
1. dp[i][0] 表示持有股票的最大金额，dp[i][1] 表示不持有股票的最大金额，表示盈利结果
2. 递推公式由前一天持有金额和是否买股票决定
决定是否花钱买入股票 dp[i-1][0] = max(dp[i-1][0], -price[i])
股票最大盈利 dp[i-1][1]=max(dp[i-1][1], dp[i-1][0] + price[i])
3. Dp 初始化都是从 dp[0][0]\[1] 推出
dp[0][0]=-price[0] 第一天就持有股票的最大金额
dp[0][1]=0 第一天不持有股票，那就为 0
4. 遍历顺序从前往后
5. 打印 dp

int maxProfit(vector<int>& prices) {// 定义dp数组std::vector<std::vector<int>> dp(prices.size(), std::vector<int>(2,0));// 初始化dp 0 持有股票的金额 1 不持有股票的金额dp[0][0] = -prices[0];dp[0][1] = 0;// 遍历dpfor (int i = 1; i < prices.size(); ++i) {// 如果要买今天的股票 那种方式金额最多dp[i][0] = std::max(dp[i-1][0], -prices[i]);// 不持有股票最大金额（不持有或者卖出(持有成本+卖出)求最大）dp[i][1] = std::max(dp[i-1][1], dp[i-1][0] + prices[i]);}return std::max(dp[prices.size()-1][0], dp[prices.size()-1][1]);
}

122. 买卖股票的最佳时机 II - 力扣（LeetCode）
有贪心算法与 dp 两种，贪心算法就是吃干净每个 T，有波动就吃，波动小于 0 不操作
详情见 [[Day28 贪心Ⅱ 股票交易跳跃游戏 K取反]]
1. Dp 数组定义如上题，dp[i][0] 表示持有股票最大金额，dp[i][1] 表示不持有股票的最大金额
2. 递推公式的确定类似上题，本题中可以多次买卖股票了，因此持有股票的最大金额是多次变换的
本题目说了只能持有或卖出两个状态，不存在持有卖一半的情况，因此持有之前一定是不持有的
持有的最大金额：取持有或者新买入的最大 dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])
不持有的最大金额：dp[i][0]=max(dp[i-1][1], dp[i-1][0]+prices[i])
3. 初始化 dp 从 0 推出，因此 dp[0][0]=-prices[0],dp[0][1]=0
4. 遍历顺序从前往后遍历
5. 打印 dp

int maxProfit(vector<int>& prices) {// 定义dp数组 0 表示持有股票的最大金额 1 表示不持有股票的最大金额std::vector<std::vector<int>> dp(prices.size(), std::vector<int>(2,0));// 初始化dp数组dp[0][0] = -prices[0];dp[0][1] = 0;// 遍历dp数组for (int i = 1; i < prices.size(); ++i) {// 更新两个dp分量 持股最大金额 不持股最大金额 取之前的状态与决定持股/不持股的状态最大值dp[i][0] = std::max(dp[i-1][0], dp[i-1][1]-prices[i]);dp[i][1] = std::max(dp[i-1][1], dp[i-1][0]+prices[i]);}return std::max(dp[prices.size()-1][0], dp[prices.size()-1][1]);
}

123. 买卖股票的最佳时机 III - 力扣（LeetCode）
基于上一题的升级版，有两次买卖机会，可以买卖一次，卖两次，不买卖
在上一题基础上多添加几个状态
1. Dp 数组定义
第 i 天不操作 dp[i][0]，第 i 天第一次持有 dp[i][1]，第 i 天第一次不持有 dp[i][2]，
第 i 天第二次持有 dp[i][3]，第 i 天第二次不持有 dp[i][4]
2. 递推公式可以看作是之前题目的扩展版，多了一次买入卖出情况
不操作 dp[i][0]=dp[i-1][0]
第一次持有 dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i])
第一次不持有 dp[i][2]=max(dp[i-1][2], dp[i-1][1]+prices[i])
第二次持有 dp[i][3]=max(dp[i-1][3], dp[i-1][2]-prices[i])
第二次不持有 dp[i][4]=max(dp[i-1][4], dp[i-1][3]+prices[i])
3. 初始化 dp
不操作 dp[0][0]=0
第一次持有 dp[0][1]=-prices[0]
第一次不持有 dp[0][2]=dp[0][1]+prices[0]=0
第二次持有 dp[0][3]=dp[0][2]-prices[0]=-prices[0]
第二次不持有 dp[0][4]=dp[0][4]+prices[0]=0
4. 遍历顺序从前往后推导出来的
5. 打印 dp
结果最后只存在 2 4 中，因为卖出的金额一定比买入金额高，取两次卖出的最大值
本质上第二次卖出就是最大值，因为第二次卖出包含了第一次卖出的情况

int maxProfit(vector<int>& prices) {// 定义dp数组std::vector<std::vector<int>> dp(prices.size(), std::vector<int>(5,0));// dp赋值 0 不操作 1 第一次持有 2 第一次不持有 3 第二次持有 4 第二次不持有dp[0][0] = 0;dp[0][1] = -prices[0];dp[0][2] = 0;dp[0][3] = -prices[0];dp[0][4] = 0;// 遍历dpfor (int i = 1; i < prices.size(); ++i) {dp[i][0] = dp[i-1][0];dp[i][1] = std::max(dp[i-1][1], dp[i-1][0]-prices[i]);dp[i][2] = std::max(dp[i-1][2], dp[i-1][1]+prices[i]);dp[i][3] = std::max(dp[i-1][3], dp[i-1][2]-prices[i]);dp[i][4] = std::max(dp[i-1][4], dp[i-1][3]+prices[i]);}return std::max(dp[prices.size()-1][2], dp[prices.size()-1][4]);
}

动态规划

题目

相关文章：