网站建设硬件配置,无锡抖音代运营公司,磁力链最佳的搜索引擎,做电影网站许可证给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。…给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
示例 1 输入[7,1,5,3,6,4] 输出5 解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。
示例 2 输入prices [7,6,4,3,1] 输出0 解释在这种情况下, 没有交易完成, 所以最大利润为 0。
思路
买卖股票除了确定买卖日期之外还需要确定当天股票的状态
股票状态有两种持有和不持有 为什么不用买入和卖出来作为状态 因为买入和卖出仅能代表两种状态即买入和卖出 什么意思呢就比如第i天你卖出了股票好那第i1天如果你不买股票那应该是什么状态 如果还用“卖出”状态来表示那么就意味着第i1天仍然要卖出股票但实际上我们想表示的是这样一种状态“第i天卖出股票后如果第i1天不买那么第i天卖掉股票后的状态应该持续到第i1天” 因此使用买入和卖出来作为状态会漏掉一些状态还得单独为那些情况设定对应的状态进行表示 五步走
1、确定dp数组含义
根据思路我们需要的dp数组应该是二维的
dp[i][0]:代表第i天持有股票所得到的最大收益
dp[i][1]:代表第i天不持有股票所得到的最大收益 这里在解释一下持有和不持有 持有指的是我现在手头上有某只股票但不一定是今天买的有可能是之前某一天买的然后该状态延续到了现在 不持有指的是手头上已经没有股票了但不一定是今天卖的有可能是之前卖掉了然后该状态持续到了现在因为本题的股票只能买卖一次因此该状态会持续到最后一天 2、确定递推公式
因为dp的定义是持有和不持有两种因此这两种情况需要分开讨论
1持有股票
第i天持有股票dp[i][0]的状态可以通过两种情况推导得到
第i天买了股票第i - 1天之前买了股票
因为本题只能买卖一次股票因此不管在哪天买入股票都是第一次买入
因为我们的初始现金是0所以在买入股票之后此时的最大收益是 -price[i]即dp[i][0] -price[i]。因为买股票花钱了嘛此时的状态变为持有股票
然后如果是第i天不买入股票但状态仍是持有股票的话那么此时的状态是dp[i][0] dp[i - 1][0]
综上取两者最大的情况那么持有股票时的递推公式为dp[i][0] max(dp[i - 1][0], -price[i])
2不持有股票
第i天持有股票dp[i][1]的状态可以通过两种情况推导得到
第i天卖了股票第i - 1天之前卖了股票
如果是在第i天卖了股票那么此时除了状态需要转换为持有股票并且是i - 1天持有因为第i天卖掉了就不持有了还需要加上第i天的股价price[i]作为收益即dp[i][1] price[i] dp[i - 1][0] 也就是说如果当前的状态是不持有并且原因是那在第i天还没卖股票时此时的状态应该是dp[i][0]卖掉之后状态转变为dp[i][1] 显然不能用dp[i][1] dp[i][0]来表示这件事情 那么可以用price[i]表示第i天卖了股票因为得到了收益然后再用dp[i - 1][0]表示我前一天确实有这个股票 两件事情加起来就可以证明我在第i天卖了股票 如果是在第i - 1天之前卖了股票那么此时状态还是不持有股票即dp[i][1] dp[i - 1][1]
综上取两者最大的情况那么不持有股票时的递推公式为dp[i][1] max(dp[i - 1][1], price[i] dp[i - 1][0])
3、初始化dp数组
从两种情况下的递推公式来看dp[0][1]和dp[0][0]是递推的基础因此需要对其进行初始化
结合dp数组的定义dp[0][1]是第0天不持有股票所得到的最大收益那没有股票肯定是0啊而且我们初始资金也是0即dp[0][1]0
而dp[0][0]则是第0天持有股票所得到的最大收益因为是第0天所以不会存在前一天的情况
因此持有的股票一定是第0天购买的所以dp[0][0] -price[i]
4、确定遍历顺序
dp[i][1]由dp[0][1]推导而来因此需要顺序遍历
代码
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();if(len 0) return 0;//定义dp数组vectorvectorint dp(len, vectorint(2));//初始化dp[0][0] -prices[0];dp[0][1] 0;//遍历dp数组for(int i 1; i len ;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 dp[len - 1][1];}
};为什么返回值是dp[len - 1][1]而不是max(dp[len][0], dp[len][1]) 如果认为max(dp[len][0], dp[len][1])是返回值的话存在两个错误
1len - 1才是最后一天不是len
2题目要求最大利润但没有要求具体在哪个状态达成
在这个题目中只需要求最终的最大利润而不需要知道具体是在哪个状态持有股票或不持有股票达到了最大利润因此直接返回dp[len - 1][1]即可。这是因为题目中规定最后一天必须卖出所有持有的股票而不是可以选择继续持有。
在遍历到最后一天后dp[len-1][0]表示最后一天持有股票的最大收益而dp[len-1][1]则表示最后一天不持有股票的最大收益。
我们只需要考虑最后一天的状态也就是持有股票和不持有股票的两种情况因为最后一天无法再进行任何交易了只有卖出股票才能获得收益。因此我们只需要返回最后一天不持有股票的最大收益 dp[len-1][1] 即可。
买卖股票的最佳时机II
力扣题目链接(opens new window)
给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6-3 3 。
示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。
示例 3: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示
1 prices.length 3 * 10 ^ 40 prices[i] 10 ^ 4
思路
基本的思路和 I 一致
唯一不同的地方就是推导dp[i][0]和dp[i][0]的时候第i天买入股票的情况。
这里再推导一下所有的情况吧
1持有股票dp[i][0]
如果是第i天买入的那么要用没有持有该股票时有的钱减去股票的售价即dp[i][0] dp[i - 1][1] - prices[i]
如果是第i-1天买入的就还是和上一题一样状态延续到第i天即可即dp[i][0] dp[i - 1][0]
综上dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]);//持有
2不持有股票dp[i][1]
如果是第i天卖掉的那就要用持有该股票时有的钱加上卖股票得的钱即dp[i][1] dp[i - 1][0] prices[i]
如果是第i-1天卖掉的延续第i天的状态即可即dp[i][1] dp[i - 1][1]
综上dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i]);//不持有
代码
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();//获取prices数组长度天数if(len 0 ) return 0;vectorvectorint dp(len, vectorint(2));//创建dp数组dp[0][0] -prices[0];//初始化dp[0][1] 0;for(int i 1; i len; 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]);//不持有}return dp[len - 1][1];//最后一天要求把股票卖掉返回不持有股票的最大金钱数}
};买卖股票的最佳时机III
力扣题目链接(opens new window)
给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
示例 1: 输入prices [3,3,5,0,0,3,1,4] 输出6 解释在第 4 天股票价格 0的时候买入在第 6 天股票价格 3的时候卖出这笔交易所能获得利润 3-0 3 。随后在第 7 天股票价格 1的时候买入在第 8 天 股票价格 4的时候卖出这笔交易所能获得利润 4-1 3。
示例 2 输入prices [1,2,3,4,5] 输出4 解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4。注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。
示例 3 输入prices [7,6,4,3,1] 输出0 解释在这个情况下, 没有交易完成, 所以最大利润为0。
示例 4 输入prices [1] 输出0
提示
1 prices.length 10^50 prices[i] 10^5
思路
与之前的两题最大的不同是之前一天只可以进行一次交易买卖总的交易次数也只有1次
而现在一天可以交易两次总的次数也是两次
至多买卖两次意味着可以买卖一次可以买卖两次也可以不买卖。
五步走
1、确定dp数组含义
回忆一下之前只能买卖一次时我们有两种情况即第i天持有或不持有股票
现在因为可以进行两次买卖所以第i天可能有的所有情况假设在第i天就进行两次交易就会有四种情况有四种
0、没有操作--dp[i][0]1、第i天第一次持有股票--dp[i][1]2、第i天第一次不持有股票--dp[i][2]3、第i天第二次持有股票--dp[i][3]4、第i天第二次不持有股票--dp[i][4]
即dp[i][j]中i表示第i天j表示状态
dp[i][j]表示第i天状态j所剩最大现金
2、确定递推公式
dp[i][0]先不用管后面要初始化
达到dp[i][1]状态第一次持有股票有两个具体操作
操作一第i天买入股票了那么dp[i][1] dp[i-1][0] - prices[i]用前一天状态下还剩的钱减去第i天买入股票的价格操作二第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]第一次不持有股票同理
操作一第i天卖出股票了那么dp[i][2] dp[i - 1][1] prices[i] 操作二第i天没有操作沿用前一天卖出股票的状态即dp[i][2] dp[i - 1][2]
取最大结果dp[i][2] max(dp[i - 2][1] - prices[i], dp[i - 1][2]);
按上面的形式可以把剩余的情况在不同操作下的状态推导出来
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数组
1如果第0天没有操作那就是0即dp[0][0] 0
2如果第0天第一次操作
在第0天第一次买入初始现金为0那么现在要扣除买股票的钱即dp[0][1] -prices[0]在第0天第一次卖出即dp[0][2] 0 如果第0天的第一次操作就是卖出那此时都没有东西卖什么呢 这种情况可以理解为在同一天先买入了然后又在当天卖出 买卖都是相同的价格相当于钱花出去了又原路返回因此dp[0][2] 0 由此我们可以发现第一次卖出的操作是依赖第一次买入操作的 3如果第0天第二次操作
在第0天第二次买入。dp[0][3] -prices[0] 所谓的“第二次买入”意味着我之前已经买入过一次了也就是说第二次买入依赖于第一次卖出的状态 又因为题目规定买完必须先卖掉才能再买所以“第二次买入”时已经经过了第一次买入和卖出 因此在第0天第二次买入时手头上的钱仍然是0那么买入之后的状态自然就是 -prices[0] 在第0天第二次卖出。dp[0][4] 0 与在第0天第一次卖出同理 4、确定遍历顺序
i由i-1推出因此仍是从小到大遍历即顺序遍历
代码
class Solution {
public:int maxProfit(vectorint prices) {if (prices.size() 0) return 0;//创建dp数组vectorvectorint dp(prices.size(), vectorint(5, 0));//初始化,根据分析进行初始化dp[0][1] -prices[0];dp[0][3] -prices[0];//遍历dp数组for(int i 1; i prices.size(); i){dp[i][0] dp[i - 1][0];//不进行操作//第i天第一次进行操作dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]);//不操作|买入股票用前一天状态下还剩的钱减去第i天买入股票的价格dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i]);//不操作|卖出股票用前一天状态下还剩的钱加上第i天卖掉股票的收益//第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]);//不操作|卖出股票}return dp[prices.size() - 1][4];}
};买卖股票的最佳时机IV
力扣题目链接(opens new window)
给定一个整数数组 prices 它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
示例 1 输入k 2, prices [2,4,1] 输出2 解释在第 1 天 (股票价格 2) 的时候买入在第 2 天 (股票价格 4) 的时候卖出这笔交易所能获得利润 4-2 2。
示例 2 输入k 2, prices [3,2,6,5,0,3] 输出7 解释在第 2 天 (股票价格 2) 的时候买入在第 3 天 (股票价格 6) 的时候卖出, 这笔交易所能获得利润 6-2 4。随后在第 5 天 (股票价格 0) 的时候买入在第 6 天 (股票价格 3) 的时候卖出, 这笔交易所能获得利润 3-0 3 。
提示
0 k 1000 prices.length 10000 prices[i] 1000
思路
本题与上题的不同点在于买卖次数现在我们可以任意买卖k次了
从上题来看买卖两次已经需要列出4个状态了不算不操作状态因此在k次交易的条件下罗列处所有状态是可能的
需要使用循环去控制
五步走
1、dp数组的含义
与上一题一样
二维数组 dp[i][j] dp[i][j]表示第i天状态j所剩最大现金
j的状态可以表示为
0 表示不操作1 第一次买入2 第一次卖出3 第二次买入4 第二次卖出.....
除了0以外上述状态的规律可以总结为偶数卖出奇数买入
因为买卖次数变成k次每多一次买卖会新增两种状态所以dp数组的大小要设置为2k 1
vectorvectorint dp(prices.size(), vectorint(2 * k 1, 0));2、确定递推公式
正如上面的分析k次买卖的话是不可能都列出来所有状态的因此需要进行抽象抽象出一个通用的递推公式
先来看看上一题中两次买卖时的递推公式 dp[i][0] dp[i - 1][0];//不进行操作//第i天第一次进行操作dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]);//不操作|买入股票用前一天状态下还剩的钱减去第i天买入股票的价格dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i]);//不操作|卖出股票用前一天状态下还剩的钱加上第i天卖掉股票的收益//第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]);//不操作|卖出股票这里可以发现二维dp数组中第二个维度我们是写成具体数字的用来表示买入和卖出状态
可以使用一个变量j来代替具体的数字j 1表示买入j 2表示卖出
使用for循环控制jj从0开始循环每次自增2
for(int j 0; i 2 * k; j 2){dp[i][j] max(dp[i - 1][j 1], dp[i - 1][j] - prices[i]);//不操作|奇数买入,用前一天状态下还剩的钱减去第i天买入股票的价格dp[i][j] max(dp[i - 1][j 2], dp[i - 1][j 1] prices[i]);//不操作|偶数卖出,用前一天状态下还剩的钱加上第i天卖掉股票的收益
}类比j为奇数是买偶数是卖的状态。 为什么j是小于2 * k而不是别的值比如2 * k - 1 遇到边界不确定的情况时就代入具体值来判断是否合理 这里假设一共至多可以买卖2次 如果j 2 * k ,那么 j 4 以上面 两次买卖时的递推公式 为例来看 当循环开始 j 0所以 j 1 指向dp[i][1] j 2 指向dp[i][2]一切正常 j 2所以 j 1 指向dp[i][3] j 2 指向dp[i][4]一切正常 j 3所以 j 1 指向dp[i][3] j 2 指向dp[i][4]一切正常 j 4循环结束所有状态被完整覆盖边界正确 3、初始化dp数组
基本上与买卖III的思路一致
1如果第0天没有操作那就是0即dp[0][0] 0
2如果第0天第一次操作
在第0天第一次买入初始现金为0那么现在要扣除买股票的钱即dp[0][1] -prices[0]在第0天第一次卖出即dp[0][2] 0
3如果第0天第二次操作
在第0天第二次买入。dp[0][3] -prices[0]在第0天第二次卖出。dp[0][4] 0
关于推导的细节与注释详见买卖III
我们还是从上面初始化中总结规律进行抽象
即j为奇数时候要初始化为-prices[0]j为偶数时候要初始化为0
使用for循环进行初始化
for(int j 1; j 2 * k; j 2){dp[0][j] -prices[0];//0在创建dp数组的时候就初始化了
}为什么j是小于2 * k而不是别的值比如2 * k - 1 还是代入来看, 这里假设至多可以买卖2次那么 j 4 当j 1时奇数初始化为-prices[0] 然后自增2j 3奇数初始化为-prices[0] 再自增就超过4结束循环过程没有问题 4、确定遍历顺序
i由i-1推出因此仍是从小到大遍历即顺序遍历
代码
class Solution {
public:int maxProfit(int k, vectorint prices) {if(prices.size() 0) return 0;//创建dp数组vectorvectorint dp(prices.size() 1, vectorint(2 * k 1, 0));//初始化dp数组for(int j 1; j 2 * k; j 2){dp[0][j] -prices[0];//0在创建dp数组的时候就初始化了所以不用在此处初始化}//遍历dp数组for(int i 1; i prices.size(); i){for(int j 0; j 2 * k; j 2){//不操作|奇数买入,用前一天状态下还剩的钱减去第i天买入股票的价格dp[i][j 1] max(dp[i - 1][j 1], dp[i - 1][j] - prices[i]);//不操作|偶数卖出,用前一天状态下还剩的钱加上第i天卖掉股票的收益dp[i][j 2] max(dp[i - 1][j 2], dp[i - 1][j 1] prices[i]);}}return dp[prices.size() - 1][2 * k];//返回最后一天卖掉股票后的总金额}
};
