服装效果图网站,零食网站页面模板,做网站建设科技公司,百度搜索引擎原理Leetcode股票问题总结篇 动态规划的股票问题一共六道题#xff0c;买卖股票最佳时机和买卖股票手续费都是一个类型的问题#xff0c;维护好买入和卖出两个状态即可#xff0c;方法一摸一样。而冷冻期也差不多就是状态多了点#xff0c;买入、保持卖出、当日卖出、以及冷冻期…Leetcode股票问题总结篇 动态规划的股票问题一共六道题买卖股票最佳时机和买卖股票手续费都是一个类型的问题维护好买入和卖出两个状态即可方法一摸一样。而冷冻期也差不多就是状态多了点买入、保持卖出、当日卖出、以及冷冻期四个状态。做题方法还是动态规划五部曲 明确dp数组含义这里六道题全部第i天都是手里买入状态或者卖出状态的现金数是多少这篇文章下标0代表未持有下标1代表持有。写出递推公式下面写了最基本的其他题的公式都是在这个基础上做了修改的 dp[i][0] max(dp[i - 1][0], dp[i - 1][1] prices[i]);dp[i][1] max(dp[i - 1][1], -prices[i]);最佳时机2那道题就是在这个基础上修改买入时的递推公式为dp[i][1] max(dp[i - 1][1], dp[i - 1][0]-prices[i - 1]);最佳时机3那道题是增加两个状态表示第二次买入和卖出 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]);最佳时机4那道题是增加到2 * k个状态那么内层就要变为双层循环为各个状态赋值了。 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);dp[i][j 1] max(dp[i - 1][j 1], dp[i - 1][j] prices[i]);冻结期那道题的递推公式就稍微复杂了需要维护四个状态分别是买入、保持卖出、当日卖出、以及冷冻期。 dp[i][0] max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);dp[i][1] max(dp[i - 1][1], dp[i - 1][3]);dp[i][2] dp[i - 1][0] prices[i];dp[i][3] dp[i - 1][2];含手续费这道题和第二道题一摸一样在卖出时减去手续费就行。 初始化每次买入的时候必须初始化为-price[0]其他赋值为0即可。遍历顺序由于需要用到 i - 1的资金所以从前往后遍历
121. 买卖股票的最佳时机
力扣题目链接
代码实现
int maxProfit(vectorint prices) {vectorvectorint dp(prices.size() 1, vector(2, 0));dp[1][0] 0, dp[1][1] -prices[0];//二维数组0代表不持有1代表持有for (int i 2; i prices.size(); i) {dp[i][0] max(dp[i - 1][0], dp[i - 1][1] prices[i - 1]);dp[i][1] max(dp[i - 1][1], -prices[i - 1]);}return dp[prices.size()][0];}动态规划二维数组滚动数组优化方式
int maxProfit(vectorint prices) {vectorvectorint dp(2, vector(2, 0));//只记录当前天和前一天的状态即可dp[0][0] 0, dp[0][1] -prices[0];//二维数组0代表不持有1代表持有for (int i 1; i prices.size(); i) {dp[i % 2][0] max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] prices[i]);dp[i % 2][1] max(dp[(i - 1) % 2][1], -prices[i]);//看实现通过求余每次取的都是前一个元素值}return dp[(prices.size() 1) % 2][0];//用1因为数组可能为空}动态规划一维数组实现法比二维实现更简洁
int maxProfit(vectorint prices) {vectorint dp(2, 0);//只记录当前天的状态即可dp[0] 0, dp[1] -prices[0];//0代表不持有1代表持有for (int i 1; i prices.size(); i) {dp[0] max(dp[0], dp[1] prices[i]);dp[1] max(dp[1], -prices[i]);}return dp[0];}贪心法实现每次更新左边界为最小值然后不断更新result结果
int maxProfit(vectorint prices) {int low INT_MAX, result 0;for (int i 0; i prices.size(); i) {low min(low, prices[i]);result max(result, prices[i] - low);}return result;}买卖股票的最佳时机2
力扣题目链接 思路
在上题基础上增加了买卖次数修改买入时的计算方法即可。
代码实现
普通动态规划想法直接计算每天的利润和贪心类似
int maxProfit(vectorint prices) {//dp[i] max(dp[i - 1], dp[i - 1] prices[i] - prices[i - 1]);vectorint dp(prices.size(), 0);for (int i 1; i prices.size(); i) {dp[i] max(dp[i - 1], dp[i - 1] prices[i] - prices[i - 1]);} return dp[prices.size() - 1];}用双状态实现的方法这里用一维数组实现的也可以是二维
int maxProfit(vectorint prices) {vectorint dp(2, 0);dp[0] 0, dp[1] -prices[0];for (int i 1; i prices.size(); i) {dp[0] max(dp[0], dp[1] prices[i]);dp[1] max(dp[1], dp[0] - prices[i]);}return dp[0];}贪心法
int maxProfit(vectorint prices) {int profit 0;for (int i 1; i prices.size(); i) {profit max(prices[i] - prices[i - 1], 0);}return profit;}双指针法
int maxProfit(vectorint prices) {int profit 0, buy_index 0;for (int i 0; i prices.size() - 1; i) {if (prices[i] prices[i 1]) {profit prices[i] - prices[buy_index];buy_index i 1;continue;}if (i 1 prices.size() - 1) {profit prices[i 1] - prices[buy_index];}}return profit;}买卖股票的最佳时机3
力扣题目链接 思路
这道题规定只能买卖两次实现方法上面已经写过了直接上代码
代码实现
int maxProfit(vectorint prices) {vectorvectorint dp(prices.size(), vectorint(5, 0));dp[0][1] -prices[0], dp[0][3] -prices[0];//相当于当天买卖一次后再次买入for (int i 1; i prices.size(); i) {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]);}return dp[prices.size() - 1][4];}买卖股票的最佳时机4
力扣题目链接
思路 买卖次数规定为k次需要利用循环给每次买卖赋值。
代码实现
int maxProfit(int k, vectorint prices) {vectorvectorint dp(prices.size(), vectorint(k * 2 1, 0));for (int i 1; i 2 * k 1; i 2) {dp[0][i] -prices[0];}for (int i 1; i prices.size(); i) {for (int j 1; j 2 * k - 1; j 2) {dp[i][j] max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);dp[i][j 1] max(dp[i - 1][j 1], dp[i - 1][j] prices[i]);}}return dp[prices.size() - 1][2 * k];}买卖股票的最佳时机含冷冻期
力扣题目链接 题目描述 在第二题基础上增加了冷冻期需要维护四个状态
代码实现
int maxProfit(vectorint prices) {int len prices.size();vectorvectorint dp(len, vectorint(4, 0));dp[0][0] -prices[0];for (int i 1; i len; i) {dp[i][0] max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);dp[i][1] max(dp[i - 1][1], dp[i - 1][3]);dp[i][2] dp[i - 1][0] prices[i];dp[i][3] dp[i - 1][2];}return max(dp[len - 1][1], max(dp[len - 1][2], dp[len - 1][3]));}买卖股票的最佳时机含手续费
力扣题目链接 题目描述 和第二题基本一样卖出时减去手续费就行了
代码实现
int maxProfit(vectorint prices, int fee) {vectorvectorint dp(prices.size(), vectorint(2, 0));dp[0][1] -prices[0];for (int i 1; i prices.size(); i) {dp[i][0] max(dp[i - 1][0], dp[i - 1][1] prices[i] - fee);dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[prices.size() - 1][0];}
