淘先锋技术网

首页 1 2 3 4 5 6 7

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

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

示例 2:

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

分析

当题目中 k k k大于表格数量的 1 2 \frac{1}{2} 21的时候,就相当于无限制了,这个时候采用贪心算法更好。否则就得用动态规划。

动态规划

根据上篇介绍动态规划设计的方法, d p ( p , k ) dp(p,k) dp(p,k)应该代表着当数组为p时候最多完成k笔交易,所能获得的最大利润。然后找这个问题中股民遇到的选择情景,股民每一天都可以选择买与不买,卖与不卖,通过这些选择来使自己利益最大化,需要注意的是买与不买是在自己不持股票的状态下,卖与不卖是在自己持股的状态下。所以每一天的两种状态都在dp范围内。

假设股民在i-1天之前在两种情况下都已经是做出了自己最优的选择了,那么在第i天我们应该如何做出抉择呢?
我们假设 d p ( i , j ) dp(i,j) dp(i,j)代表包括第i天的前i天的股票给最大j笔交易机会,且当前不持股情况下,最大利润能是多少。很明显这和原问题是同样的结构。 这里包含了第i天的选择操作。
我们再假设 h o l d ( i , j ) hold(i,j) hold(i,j)代表包括第i天的前i天的股票给最大j笔交易机会,且当前持股情况下,你目前的最大金钱数能是多少。这里和上面的区别在于,在这之前你是花了前买了一个股票的,至于是第i天买的还是更早买的,无所谓了。

我们要让股民利益最大化,在第i天要做出选择:

  • 在当天不持股的情况下,说明要么他本来就不持股,要么说明他今天卖掉了自己的股票,消耗了一次交易机会,我们选择一个能让他利益最大的情况
    d p ( i , j ) = m a x ( d p ( i − 1 , j ) , h o l d ( i − 1 , j − 1 ) + p [ i ] ) dp(i,j)=max(dp(i-1,j),hold(i-1,j-1)+p[i]) dp(i,j)=max(dp(i1,j),hold(i1,j1)+p[i])
  • 在当天持股的情况下,说明要么他本来就持股,要么说明他今天买了股票,我们选择一个能让他利益最大的情况
    h o l d ( i , j ) = m a x ( h o l d ( i − 1 , j ) , d p ( i − 1 , j ) − p [ i ] ) hold(i,j)=max(hold(i-1,j),dp(i-1,j)-p[i]) hold(i,j)=max(hold(i1,j),dp(i1,j)p[i])

写出表达式后我们要计算初始值:
d p ( 0 , j ) = 0 , j = 0 , 1 , 2... k h o l d ( 0 , j ) = − p [ 0 ] , j = 0 , 1 , 2... k d p ( i , 0 ) = 0 , i = 0 , 1 , 2... p . s i z e − 1 dp(0,j)=0,j=0,1,2...k\\ hold(0,j)=-p[0],j=0,1,2...k\\ dp(i,0)=0,i=0,1,2...p.size-1\\ dp(0,j)=0,j=0,1,2...khold(0,j)=p[0],j=0,1,2...kdp(i,0)=0,i=0,1,2...p.size1

贪心算法

贪心比dp要容易,当 k k k大于表格数量的 1 2 \frac{1}{2} 21的时候,我们认为是无限制买卖。所以只要是涨价,我们都买。把原数列差分,然后把大于0的都加起来就是。

c++代码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp,hold;
        if(prices.size()==0)return 0;
        if(k>prices.size()/2){
            return greedy(prices);
        }
        dp=vector<vector<int>>(prices.size(),vector<int>(k+1,0));
        hold=vector<vector<int>>(prices.size(),vector<int>(k+1,0));

        for(int i=0;i<=k;i++){
            hold[0][i]=-prices[0];
        }
        for(int i=1;i<prices.size();i++){
            hold[i][0]=max(hold[i-1][0],-prices[i]);
        }
         
        for(int i=1;i<prices.size();i++){
            for(int j=1;j<=k;j++){
                dp[i][j]=max(dp[i-1][j],hold[i-1][j-1]+prices[i]); 
                hold[i][j]=max(hold[i-1][j],dp[i-1][j]-prices[i]);
            }
        }

        return dp[prices.size()-1][k];
    }

    int greedy(vector<int>& prices){
        int ans=0;
        for(int i=0;i<prices.size()-1;i++){
            ans+=max(0,prices[i+1]-prices[i]);
        }
        return ans;
    }
};

我的博客:https://kidtic.gitee.io/blog/