LeetCode No.188 股票

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

LeetCode上面有好几道股票的动态规划题目，实际上这些题目都差不多，只要我们掌握了最难的那个，后面基本没问题。
首先是状态变量的定义：
dp[i] 最粗糙的就是这样子，dp[i]代表第i天的最大利润
但是实际写下去我们会发现，仅仅一维数组是没有用的，因为缺少了很多中间状态。比如第i天的利润无法直接从第i-1中获取，中间夹杂着是否持有股票，交易次数等的限制。所以接下来我们在状态变量上面增加几个标志
dp[i][k][a]:i表示天数，k表示交易次数，a表示是否持有股票（持有为1反之为0）
接下来就是状态转移方程：

第i天没有持有股票的时候,存在两种情况:

  1. 第i-1天的时候就已经没有持有股票了
  2. 第i天的时候将股票抛售
    即：
    dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])

第i天持有股票的时候,同样存在两种情况:

  1. 第i-1天的时候持有股票
  2. 第i天的时候将购入股票,这时候因为发生了交易,所以应该转移的状态是前一天的k-1次交易时没有持有股票的状态
    即：
    dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])

代码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(k<=0||prices.size()<=1)
        {
            return 0;

        }
        if(k>prices.size()/2)
        {
            return maxProfit(prices);  //当输入的k过大的时候就已经转换为无限次交易的题目
        }
        vector<vector<vector<int> > > dp(prices.size(),vector<vector<int> >(k+1,vector<int>(2)));
        int maxprofit=0;
        for(int i=0;i<prices.size();i++)
        {
            for(int j=1;j<=k;j++)
            {
                if(i-1<0)
                {
                    dp[i][j][0]=0;
                    dp[i][j][1]=-prices[i];
                    continue;
                }  //这里需要对一些状态进行过滤
                dp[i][j][0]=max(dp[i-1][j][1]+prices[i],dp[i-1][j][0]);
                dp[i][j][1]=max(dp[i-1][j-1][0]-prices[i],dp[i-1][j][1]);

                maxprofit=max(maxprofit,dp[i][j][0]);
            }
            
        }
        return maxprofit;
    }
    int maxProfit(vector<int>& prices)  //无限制次数交易的题目代码
    {
        int dp[2][2],x;
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for(int i=1;i<prices.size();i++)
        {
            x=i%2;
            dp[x][0]=max(dp[!x][0],dp[!x][1]+prices[i]);
            dp[x][1]=max(dp[!x][1],dp[!x][0]-prices[i]);
        }
        return dp[x][0];
    }
};

感想

股票这边看了很久，反复的去看教程。事实上我的代码并不高效，只能是勉强过了，题解中大佬们基本都是几ms的，但是这个思路是最为朴素的动态规划，更适合刚入门学习动态规划的人。一开始并不是很能理解多维dp中有些维数的作用，事实上这些有些维数（最多应该也就3了吧…再多就得还算法了）起到的作用是用来分解状态的。例如股票这道题目，题目的限制条件有：交易k次，不能同时参与多个交易 =====> 意味着要抛售前必须有股票，交易次数必须小于k次（废话），但是如果只有一个dp[n]一维数组的大小，很难界定说上个状态是否有股票，交易次数现在是否小于k次了，动态规划的核心就是记忆化，保存每一次递推的结果用于下一次。但是题目中最初的状态都可以分为：持有股票、没有持有股票、交易了、没有交易，可以说并不唯一，所以需要多维度来帮助表达限制条件，最直观的就是0表示没有股票，1表示持有股票。