从“股票问题”谈动态规划问题的解决思路

时间:2020-04-25 wunsiang 人气:1

总体思路

有过在Leetcode上练习经历的同学们对股票问题肯定不会感到陌生，动态规划问题的核心在于寻找状态转移方程，对于常规的动态规划问题，如零钱问题、背包问题，我们可能会觉得状态转移方程找起来并不费劲，但对于股票问题，可能很多同学都觉得状态转移方程难找。在我对股票问题进行了反复研究之后，我发现其实之所以股票系列分析存在这种困难，并不是“转移方程难找”，而是其具有多个维度的“状态”，其状态的复杂性导致我们在没有处理好状态的情况下便谈不上解决“转移方程”的问题。

状态的确定与处理？

首先我们要考虑的是状态有哪些，具体到本题，共有三个维度的状态：

天数
允许交易的最大次数
用户账户当前状态（持有或者未持有股票）

其次是如何处理状态，其实大家可以细细回想，对于动态规划问题我们处理状态，虽然你可能没有注意，其实使用的是“穷举”思想，比如说背包问题中的物品数量和背包容量。至于怎么枚举，看下面的伪代码你肯定就明白啦！

for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)

该伪代码参考自Leetcode，个人认为这个状态枚举思路的伪代码写的非常好，但是作者对于股票问题状态划分有些复杂。
那具体到本题，我们的状态框架如下

dp[i][k][0 or 1] //前面说了三个维度，自然dp数组也是三维的
for(int i = 0;i < n;i++)
    for(int j = 0;j < k;j++)
        dp[i][j][0] 取优
        dp[i][j][1] 取优//账户状态这个维度只有两种可能，就直接计算就好啦。

那我们接下里将通过对股票问题的具体实例讲解的方式来介绍具体解法，目前剩下的其实就是个状态转移方程的事情啦。

各个击破

k = 1的情况

121. 买卖股票的最佳时机
k = 1是思路很清晰，其实只需要直接一趟遍历，并且记录下当前元素之前的最小元素并利用其计算当前天卖出最大收益即可。这个其实感觉不算典型动态规划。


class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0)
            return 0;
        int min = prices[0],max = 0;
        for(int i = 1;i < prices.length;i++){
            max = Math.max(max,prices[i] - min);
            min = Math.min(min,prices[i]);
            
        }
        return max;
    }
}

k值不受限

122. 买卖股票的最佳时机 II

枚举框架

按照我们最开始的状态枚举框架，k不受限即从前向后遍历（了解完全背包问题的同学肯定熟悉），并且不设置k维度即可（只有天数、账户状态两个维度）。

状态转移方程

当前天未持有，则有两种情况：
1、昨天就未持有，今天也不买，则为dp[i - 1][0]
2、昨天持有，今天卖出，则为dp[i - 1][1] + prices[i])
综上，二者取优
dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i]);
同样，当前天持有也是两种情况：
1、昨天持有，则为dp[i - 1][1]
2、昨天未持有，今天买入dp[i - 1][0] - prices[i]
综上，二者取优
dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];//0为未持有，1为持有
        dp[0][0] = 0;
        dp[0][1] = 0 - prices[0];
        for(int i = 1;i < prices.length;i++){
            dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

k值不受限且包含冷冻期

309. 最佳买卖股票时机含冷冻期

枚举框架

状态转移方程

当前天未持有，则有两种情况：
1、昨天就未持有，今天也不买，则为dp[i - 1][0]
2、昨天持有，今天卖出，则为dp[i - 1][1] + prices[i - 1])，注意，price从0开始索引
综上，二者取优
dp[i][0] = Math.max(dp[i - 1][1] + prices[i - 1],dp[i - 1][0]);
同样，当前天持有也是两种情况，但由于存在冷冻期，买出的话需要从i-2转移过来：
1、昨天持有，则为dp[i - 1][1]
2、昨天未持有，今天买入dp[i - 2][0] - prices[i - 1]
综上，二者取优
dp[i][1] = Math.max(dp[i - 1][1],i - 2 >= 0 ? dp[i - 2][0] - prices[i - 1]: 0 - prices[i - 1])

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length + 1][2];
        dp[0][1] = Integer.MIN_VALUE;
        for(int i = 1;i <= prices.length;i++){
            dp[i][0] = Math.max(dp[i - 1][1] + prices[i - 1],dp[i - 1][0]);
            dp[i][1] = Math.max(dp[i - 1][1],i - 2 >= 0 ? dp[i - 2][0] - prices[i - 1]: 0 - prices[i - 1]);
        }
        return dp[prices.length][0];
    }
}

k值不受限且包含手续费

状态转移方程与k值不受限完全相同，只是卖出时要减手续费即可

枚举框架

状态转移方程

当前天未持有，则有两种情况：
1、昨天就未持有，今天也不买，则为dp[i - 1][0]
2、昨天持有，今天卖出，则为dp[i - 1][1] + prices[i] - fee)
综上，二者取优
dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee);
同样，当前天持有也是两种情况：
1、昨天持有，则为dp[i - 1][1]
2、昨天未持有，今天买入dp[i - 1][0] - prices[i]
综上，二者取优
dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];//0为未持有，1为持有
        dp[0][0] = 0;
        dp[0][1] = 0 - prices[0];
        for(int i = 1;i < prices.length;i++){
            dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

k为任意整数

188. 买卖股票的最佳时机 IV

枚举框架

枚举框架与本文最开始分析的思路完全相同，只需要对天、最大交易次数、账户状态这三个维度进行枚举即可。

状态转移方程

当前天未持有，则有两种情况：
1、昨天就未持有，今天也不买，且显然这种情况不会增加交易次数，则为dp[i - 1][j][0]
2、昨天持有，今天卖出，卖出操作并不会增加交易次数，仍然是本交易次数维度进行转移，为dp[i - 1][j][1] + prices[i]
综上，二者取优
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
同样，当前天持有也是两种情况：
1、昨天持有，则为dp[i - 1][j][1]
2、昨天未持有，今天买入，注意买入会引起交易次数变化，所以为dp[i - 1][j - 1][0] - prices[i]
综上，二者取优
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices == null || prices.length < 2)
            return 0;
        int[][][] dp = new int[prices.length][k + 1][2];//0是未持有，1是持有
        for(int i = 0;i <= k;i++){//第一天base case
            dp[0][i][1] = 0 - prices[0];
        }
        for(int i = 1;i < prices.length;i++){
            for(int j = 1;j <= k;j++){
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[prices.length - 1][k][0];
    }
}

总结

看到这里，其实我们就会明白，动态规划其实要确定的三部分就是:

dp语义
状态枚举框架
转移方程

确定了这三样，一切便都迎刃而解了。

加载全部内容