目录
简介
分析
总结
简介
leetcode上面有几个关于买卖股票的动态规划题。下面我们来看这种问题的模型：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。这里说的K笔交易是一次买入和一次卖出！！！
分析
我们可以用三维DP去记录解决这个问题。
dp[i][k][0] = max( dp[i-1][k][0], dp[i-1][k][1] + a[i] )//卖出的时候，次数不变
dp[i][k][1] = max( dp[i-1][k][1], dp[i-1][k-1][0] - a[i] ) //买入的时候次数-1. 这里的是我们的约定，其实也可以反过来(卖出的时候-1次数)
第一维：表示第i天
第二维：表示当前最多进行k次交易
第三维：当前是否持有股票 1：持有，0：没有持有
递推式很容易理解，但是K值要分类讨论一下：
解法1: 当K为无穷大的时候，也就是可以无限交易的时候。无限交易的时候我们可以考虑贪心去解决，很显然，见好就收即可达到最优解。
解法2: 把上面的递推式令k=1,可得
dp[i][0] = max(dp[i-1][0],dp[i-1][1] + a[i]);
dp[i][1] = max(dp[i-1][1],dp[i-1][0] - a[i]);
122. 买卖股票的最佳时机 II
class Solution {
public:int maxProfit(vector<int>& a) {int n = a.size();int ans = 0;for(int i = 1;i<n;++i){if(a[i] > a[i-1])ans += a[i] - a[i-1];//见好就收即可达到最优解}return ans;}
};class Solution {
public:// dp[i][0] = max(dp[i-1][0],dp[i-1][1] + a[i]);// dp[i][1] = max(dp[i-1][1],dp[i-1][0] - a[i]);int maxProfit(vector<int>& a) {int n = a.size();if(!n)return 0;int dp_1,dp_0;for(int i = 0;i<n;++i){if(i == 0){dp_1 = -a[i];dp_0 = 0;continue;}int tmp = dp_0;dp_0 = max(dp_0,dp_1 + a[i]);dp_1 = max(dp_1,tmp - a[i]);}return dp_0;}
};
所以原问题的解题思路：
当k >= n/2，都可以认为我们可以无限交易，可以采用上述贪心的方式；
当k < n/2 ，采用上述动态规划思路
188. 买卖股票的最佳时机 IV
class Solution {
public:int maxProfit(int k, vector<int> &prices) {if (prices.empty()) return 0;if (k >= prices.size()/2) return solveMaxProfit(prices);//贪心解决int n = prices.size();vector<vector<vector<int> > > dp(n,vector< vector<int> >(k+1,vector<int>(2,0)));for(int i = 0;i<n;++i)for(int j = 1;j<=k;++j){if(i == 0) {dp[i][j][0] = 0;dp[i][j][1] = -prices[i];continue;}dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1] + prices[i]);dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0] - prices[i]);}return dp[n-1][k][0];}int solveMaxProfit(vector<int> &prices) {int res = 0;for (int i = 1; i < prices.size(); ++i) {if (prices[i] - prices[i - 1] > 0) {res += prices[i] - prices[i - 1];}}return res;}
};
总结
leetcode这道题的变种有好多道：
只能进行一次交易：最低点买入，最高点卖出即可
含手续费：在上面的递推式加上手续费即可
我认为先写上面两道题才能看清这道题的本质！