网站设计论文的摘要,wordpress 锚点定位,宁波制作网页服务好,wordpress的静态数据总结一下#xff0c;买卖股票系列的动态规划思想#xff0c;贪心解法或者其他解法不做描述。
总结
121. 买卖股票的最佳时机 只有一次交易机会#xff0c;每天有两种状态#xff1a;持有股票和不持有股票#xff1b;
122. 买卖股票的最佳时机 II 有多次交易机会#x…总结一下买卖股票系列的动态规划思想贪心解法或者其他解法不做描述。
总结
121. 买卖股票的最佳时机 只有一次交易机会每天有两种状态持有股票和不持有股票
122. 买卖股票的最佳时机 II 有多次交易机会每天有两种状态持有股票和不持有股票
123. 买卖股票的最佳时机 III 至多两次交易机会每天有 2*24 种状态第一次持有股票第一次不持有股票第二次持有股票第二次不持有股票
188. 买卖股票的最佳时机 IV - 力扣LeetCode至多 k 次交易机会与买卖股票 3 相比每天有 2*k2k 种状态第一次持有股票第一次不持有股票第二次持有股票第二次不持有股票... 第 k 次持有股票第 k 次不持有股票。
买卖股票的最佳时机 Ⅰ 题目描述给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。 买卖股票系列的第一题核心是只有一次交易机会。 dp 数组建立
用两个 dp 数组来描述
dp[i][0] 第 i 天持有股票的最大剩余现金dp[i][1] 第 i 天不持有股票的最大剩余现金。
重要的是理解这里的“剩余现金”是什么含义一开始我们持有的现金为 0买入一支股票i后我们持有股票的剩余现金就是-prices[i]而在第 ik 天卖出股票后我们不持有股票的剩余现金就是 prices[ik] - prices[i]也就是交易后的利润。
dp[0][0] -prices[0]; 因为第 0 天要持有股票只能购入第一支股票剩余现金为 -prices[0]
dp[0][1] 0; 因为第 0 天只能买入股票无法卖出股票因此 dp[0][1] 初始化为 0。 递推公式
dp[i][0] max(dp[i-1][0], -prices[i]);第 i 天持有股票有两种情况 第一种第 i 天不买入股票那么第 i天持有股票的剩余现金就是第 i-1天持有股票的剩余现金即dp[i][0] dp[i-1][0];第二种第 i 天买入股票那么第 i天持有股票的剩余现金就是 0 减去第 i 天的股票价格即dp[i][0] -prices[i];两者取最大值。
dp[i][1] max(dp[i-1][1], prices[i] dp[i-1][0]);同样有两种情况 第一种第 i 天前已经不持有股票那么第 i天持有股票的剩余现金就是第 i-1天持有股票的剩余现金即dp[i][1] dp[i-1][1];第二种第 i 天当天才不持有股票那么第 i天持有股票的剩余现金就是第 i 天的股票价格 第 i-1 天持有股票的最大剩余现金即dp[i][1] prices[i] dp[i-1][0];两者取最大值。 完整代码
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();// dp[i][0] 第 i 天持有股票的最大剩余现金// dp[i][1] 第 i 天不持有股票的最大剩余现金。vectorvectorint dp(n, vectorint(2, 0));dp[0][0] -prices[0];dp[0][1] 0;for (int i 1; i n; i) {dp[i][0] max(dp[i - 1][0], -prices[i]);dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);}return dp[n - 1][1];}
};
买卖股票的最佳时机 Ⅱ 给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。 在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。 返回 你能获得的 最大 利润 。 买卖股票系列的第二题和第一题的不同之处在于可以多次买卖股票。
dp 数组建立
用两个 dp 数组来描述
dp[i][0] 第 i 天持有股票的最大剩余现金dp[i][1] 第 i 天不持有股票的最大剩余现金。
dp[0][0] -prices[0]; 因为第 0 天要持有股票只能购入第一支股票剩余现金为 -prices[0]
dp[0][1] 0; 因为第 0 天不管是不买股票还是买了再卖出股票都无法获得利润因此 dp[0][1] 初始化为 0。 递推公式
dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i]);第 i 天持有股票有两种情况 第一种第 i 天不买入股票那么第 i天持有股票的剩余现金就是第 i-1天持有股票的剩余现金即dp[i][0] dp[i-1][0];第二种第 i 天买入股票那么第 i-1 天就不能持有股票因为在这道题目中连续购买两支股票没有意义只会多花钱。第 i天持有股票的剩余现金就是 第 i-1 天不持有股票的最大剩余现金减去第 i 天的股票价格即dp[i][0] dp[i-1][1] - prices[i];两者取最大值。
dp[i][1] max(dp[i-1][1], prices[i] dp[i-1][0]);同样有两种情况 第一种第 i 天前已经不持有股票那么第 i天持有股票的剩余现金就是第 i-1天持有股票的剩余现金即dp[i][1] dp[i-1][1];第二种第 i 天当天才不持有股票同理第 i-1 天必须是持有股票的没有持有股票怎么卖出股票呢第 i天持有股票的剩余现金就是第 i 天的股票价格 第 i-1 天持有股票的最大剩余现金即dp[i][1] prices[i] dp[i-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][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);}return dp[prices.size() - 1][1];}
};
总结
本题和121. 买卖股票的最佳时机的代码几乎一样唯一的区别在
dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
因为本题的股票可以买卖多次 所以买入股票的时候剩余现金可能包含之前买卖的所得利润dp[i - 1][1]所以 dp[i][0] 可能会等于 dp[i-1][1] - prices[i]。
想到到这一点对这两道题理解的就比较深刻了。
买卖股票的最佳时机 Ⅲ 给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 这题要求我们在购入股票时手上不能持有其他股票且最多只能进行两笔交易。
前两道题同一天只有两种状态持有股票或者不持有股票
对于这道题同一天可以有 4 种状态
第一次持有股票第一次不持有股票第二次持有股票第二次不持有股票
那么 dp[i][j] 就表示第 i 天的 j 状态下的最大剩余现金。
dp[0][0] -prices[0];第 0 天第一次买入
dp[0][1] 0;
dp[0][2] -prices[0];第 0 天第二次买入第一次买入后卖出再买入有点蛇精病但是为了做题只能这么买了
dp[0][3] 0; 递推公式
第 i 天第一次持有股票的最大剩余金额 max(第 i-1 天第一次持有股票的最大剩余金额, -第 i 天股票价格)第 i 天第一次不持有股票的最大剩余金额 max(第 i-1 天第一次不持有股票的最大剩余金额, 第 i 天股票价格 第 i-1 天第一次持有股票的最大剩余金额)第 i 天第二次持有股票的最大剩余金额 max(第 i-1 天第二次持有股票的最大剩余金额, 第 i-1 天第一次不持有股票的最大剩余金额 - 第 i 天股票价格)第 i 天第二次不持有股票的最大剩余金额 max(第 i-1 天第二次不持有股票的最大剩余金额, 第 i-1 天第二次持有股票的最大剩余金额 第 i 天股票价格)
dp[i][0] max(dp[i - 1][0], -prices[i]);
dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);
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[4][4]已经包含了dp[4][2]的情况。也就是说第二次卖出的剩余现金一定是最多的。
class Solution {
public:int maxProfit(vectorint prices) {// 动态规划// 1. 第一次持有股票// 2. 第一次不持有股票// 3. 第二次持有股票// 4. 第二次不持有股票vectorvectorint dp(prices.size(), vectorint(4, 0));dp[0][0] -prices[0];dp[0][1] 0;dp[0][2] -prices[0];dp[0][3] 0;for (int i 1; i prices.size(); i) {dp[i][0] max(dp[i - 1][0], -prices[i]);dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);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]);;}int result max( dp[prices.size() - 1][1], dp[prices.size() - 1][3] );return result;}
};
买卖股票的最佳时机 Ⅳ 给你一个整数数组 prices 和一个整数 k 其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说你最多可以买 k 次卖 k 次。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 与 123. 买卖股票的最佳时机 III 不同这一次我们最多可以完成 k 笔交易
那如果按照 3 的思路我们可以用 dp[i][2 * k] 来描述第 i 天的 2k 种不同状态。
完整代码
class Solution {
public:int maxProfit(int k, vectorint prices) {// 动态规划// 1. 第一次持有股票 dp[i][0]// 2. 第一次不持有股票 dp[i][1]// 3. 第二次持有股票 dp[i][2]// 4. 第二次不持有股票 dp[i][3]// ...// k次持有 dp[i][2 * k - 2]// k次不持有 dp[i][2 * k - 1]vectorvectorint dp(prices.size(), vectorint(2 * k, 0));for (int i 0; i 2 * k; i2) {dp[0][i] -prices[0];}for (int i 1; i prices.size(); i) {// 计算第一次的两个状态dp[i][0] max(dp[i - 1][0], -prices[i]);dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);for (int j 2; j k; j) {// 计算第2次到第k次的所有状态dp[i][2 * j - 2] max(dp[i - 1][2 * j - 2], dp[i - 1][2 * j - 3] - prices[i]);dp[i][2 * j - 1] max(dp[i - 1][2 * j - 1], dp[i - 1][2 * j - 2] prices[i]);}}int result dp[prices.size() - 1][2 * k - 1];return result;}
};
