2022-04-25 17:18 北京林业大学 golang

关注

动态规划做题小结

这里写自定义目录标题

动态规划解题步骤：
例题讲解

动态规划解题步骤：

1、确定dp数组含义

2、状态转移（确定递推公式）

3、根据递推公式确定dp数组该如何初始化

4、确定循环遍历顺序

笨方法：

有时候dp数组含义好定义，但是递推公式不好找。

这时候可以找一个例子，人工把它的dp数组的表格列出来，然后根据数据加逻辑去推断。

因为很多时候仅根据一个例子中的数据得到的公式不一定有普遍性，所以不仅数据要说的通，逻辑也要说得通。

例题讲解

接下来我们将通过一组买股票的例子逐步深入探讨动态规划问题。

1、单纯股票问题

题目

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润。

示例1

输入：prices = [7,1,5,3,6,4] 输出：7 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。

示例2

输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。总利润为 4 。

示例3

输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii

解析

参考解析（方法二：贪心）：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/

1、确定dp数组含义

题目问什么就定义什么，问的是最大收益，那么dp数组的定义就是dp[i]表示前i天的最大收益。

注意： 所有讨论的开始时间不是第1天，而是第0天。例如prices = [1,2,3,4,5]，dp[0]代表股票价格为1的那一天结束时的最大收益。dp[4]则是最终的结果。

2、状态转移（确定递推公式）

递推公式一般是要确定共有多少种情况，然后分情况讨论：

第i天要么买入，要么卖出，要么什么操作也不做。

现在我们只有股票第i天的价格，那么我们可以将第i天的价格与i-1天的价格比较一下，都有哪些情况呢？

我们发现：第i天的价格要么大于第(i-1)天的价格，要么小于等于它。而这一发现有什么作用呢？

当第i天价格小于等于(i-1)天的价格时： 那么我们在第i天卖出股票就不如在第(i-1)天时卖出股票收益更高。而我们已经有了前(i-1)天的最大收益dp[i-1]，那么我们不需要考虑第(i-1)天是否有卖出股票，我们只需要知道第i天不需要卖出股票，因此前i天最大收益=前(i-1)天最大收益，即dp[i] = dp[i-1].

当第i天价格大于(i-1)天的价格时： 此时我们可以在第(i-1)天买入股票，在第i天卖出股票，这样我们得到的收益是prices[i]-prices[i-1]。同时我们又知道前(i-1)天结束时的最高收益为dp[i-1]。因此前i天结束时最高收益dp[i]=前(i-1)天结束时的最高收益+第i天的收益。即dp[i] = dp[i-1] + (prices[i]-prices[i-1]).

由此得到dp公式：

if(prices[i] > prices[i-1])
	dp[i] = dp[i-1] + (prices[i]-prices[i-1])
else
	dp[i] = dp[i-1]

3、根据递推公式确定dp数组该如何初始化

由于递推公式中计算dp[i]时需要用到dp[i-1]、prices[i-1]，所以必须满足i>0。因此我们必须初始化i=0时的情况。显然第0天结束时的最大收益为0，即dp[0] = 0。

现在我们可以验证一下递推公式是否合理，带入示例1中：

prices = [7,1,5,3,6,4] dp = [0, 0, 4, 4, 7, 7]。由此可以看出至少在示例1中是完全正确的，其实它在任何示例中都是完全正确的。

4、确定循环遍历顺序

应当从前向后遍历还是从后向前遍历呢？根据递推公式我们可以确定从前向后遍历是可取的。其实遍历顺序一般都是在第二步就要确定的，此处列出来只是给读者提个醒，在某些情况下正序遍历无法解决的时候可以试一下倒序遍历。

由此我们得出最终代码：

var maxProfit = function(prices) {
    let ans = 0;
    let n = prices.length;
    for (let i = 1; i < n; ++i) {
        ans += Math.max(0, prices[i] - prices[i - 1]);
    }
    return ans;
};
//代码有所简化，相信聪明的你可以看出，他和递归公式的含义是一样的

2、单纯*2股票问题

题目

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

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

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

示例1

输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例2

输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例3

输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例4

输入：prices = [1] 输出：0

1 <= prices.length <= 105
0 <= prices[i] <= 105

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

解析

参考解析：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-iii-by-wrnt/

这一题相比上一题的区别是，不能无数次交易了，只能有两次交易。

1、确定dp数组含义

同上，dp数组的定义就是dp[i]表示前i天的最大收益。可是，在做出这一决定后我们会发现这样的dp数组仿佛并不能解决问题。

这一题是否还可以使用上一题的方法呢，不容易用。因为第i天的状态更复杂了。

索性抛弃上一题的想法，我们来看一下第i天都有哪些状态。买入、卖出、无操作。而由于只能执行两次交易，所以我们需要记录一下第i天之前交易过几次了。

我们总结一下前i天共有以下几种状态：

未进行过任何操作；
只进行过一次买操作；
进行了一次买操作和一次卖操作，即完成了一笔交易；
在完成了一笔交易的前提下，进行了第二次买操作；
完成了全部两笔交易。

由于前i天不做任何操作收益一定为0，所以没有讨论的必要了，因此前i天的状态只剩下了后四种情况。

注意： 这里变成了前i天的状态，而不是第i天的状态了。笔者由于水平有限，在这里的转换有些唐突。不过笔者相信，读者越往后看，就会越明白的。

思考到这里，我们会发现第一步中数组定义只定义了前i天的最大收益，已经满足不了现在的需求了，所以我们重新定义一下dp数组的含义：

重新定义数组dp[prices.length][4]：

buy1[i]表示前i天只进行一次买操作的最大收益
sell1[i]表示前i天进行了一笔交易（一次买操作，一次卖操作）的最大收益
buy2[i]表示前i天进行了一笔交易+一次买操作的最大收益
sell2[i]表示前i天进行了两笔交易的最大收益

2、状态转移（确定递推公式）

由于买股票是负收益，所以递推公式如下：

buy1[i] = min(buy1[i-1], -prices[i])
sell1[i] = max(sell1[i-1], buy1[i]+prices[i])
buy2[i] = min(buy2[i-1], sell1[i]-prices[i])
sell2[i] = max(sell2[i-1], buy2[i]+prices[i])

3、根据递推公式确定dp数组该如何初始化

同上一题一样，初始化dp[0][]

dp[0][0] = -prices[0]

dp[0][1] = 0

dp[0][2] = -prices[0]

dp[0][3] = 0

4、确定循环遍历顺序

由此我们得出最终代码：

var maxProfit = function(prices) {
    const n = prices.length;
    let buy1 = -prices[0], buy2 = -prices[0];
    let sell1 = 0, sell2 = 0;
    for (let i = 1; i < n; i++) {
        buy1 = Math.max(buy1, -prices[i]);
        sell1 = Math.max(sell1, buy1 + prices[i]);
        buy2 = Math.max(buy2, sell1 - prices[i]);
        sell2 = Math.max(sell2, buy2 + prices[i]);
    }
    return sell2;
};

看完这个题，再来看这道题你应该也就对下面这道题有了解决思路了吧。

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

但是我们的股票问题并没有到此结束，还有一道更骚的题目在后面。

3、收尾股票问题

题目

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

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]输出: 0

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

解析

参考解析：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/zui-jia-mai-mai-gu-piao-shi-ji-han-leng-dong-qi-4/

1、确定dp数组含义

本题第一眼可能会以dp[i]表示前i天最高收益来定义动态数组，但是这种定义对于本题并不是很合适，所以我们先不确定dp数组，听我为你侃一侃。

由于我们最多只能持有一支股票，所以来看一下第i天一共能有几种状态：买入、卖出、不变（处于冷冻期、不处于冷冻期）。总结一下也就是以下几种状态：

目前不持有股票，且不处于冷冻期
目前不持有股票，且处于冷冻期
目前持有一支股票

因此我们来定义数组dp[prices.length][3]，其中

dp[i][0]表示第i天结束后不持有股票且不处于冷冻期的最大收益
dp[i][1]表示第i天结束后不持有股票且处于冷冻期的最大收益
dp[i][2]表示第i天结束后持有一支股票的最大收益

注意： 这里的「处于冷冻期」指的是在第 i 天结束之后的状态。也就是说：如果第 i天结束之后处于冷冻期，那么第 i+1 天无法买入股票。

2、状态转移（确定递推公式）

下面我们来分别对三种状态进行转移：

dp[i][0]：我们在第 i 天结束之后处于冷冻期的原因是在当天卖出了股票，那么说明在第 i−1 天时我们必须持有一支股票，对应的状态为 dp[i-1][0]加上卖出股票的正收益prices[i]。因此状态转移方程为：

dp[i][0] = dp[i-1][2] + prices[i]
dp[i][1]：我们在第 i 天结束之后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，即第 i−1 天时不持有任何股票：如果处于冷冻期，对应的状态为 dp[i-1][0]；如果不处于冷冻期，对应的状态为 dp[i-1][1]。因此状态转移方程为：

dp[i][1] = max(dp[i-1][0], dp[i-1][1])
dp[i][2]，我们目前持有的这一支股票可以是在第i−1 天就已经持有的，对应的状态为 dp[i−1][2]；或者是第 i 天买入的，那么第 i−1 天就不能持有股票并且不处于冷冻期中，对应的状态为 dp[i−1][1] 加上买入股票的负收益prices[i]。因此状态转移方程为：

dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i])

3、根据递推公式确定dp数组该如何初始化

同上一题一样，初始化dp[0][] dp[0][0] = -prices[0]

dp[0][1] = 0

dp[0][2] = 0

这里dp[0][1]等于0或者等于-99999都可以，他只是为了保证dp[1][2]的值是正确的。

4、确定循环遍历顺序

毫无疑问，正序遍历是可以的，我们也没有理由让他倒序遍历。

代码：

//java由于未找到js版本，只能使用java版本了。
class Solution {
    public int maxProfit(int[] prices) {
        int length = prices.length;
        int[][] dp = new int[length][3];
        if(length == 0) return 0;
        //dp[i][0]表示第i天结束时手上没有股票， 且处于冷冻期的最高收益
        //dp[i][1]表示第i天结束时手上没有股票，且不处于冷冻期的最高收益
        //dp[i][2]表示第i天结束时手上有股票的最高收益
        
        dp[0][0] = Integer.MIN_VALUE;
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        for(int i=1;i<length;i++) {

            //只有第i天卖了，这一天结束才会处于冷冻期。
            dp[i][0] = dp[i-1][2] + prices[i];

            //说明今天没卖，昨天卖没卖不知道，但是昨天一定没股票
            dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]);

            //有可能今天买的，也有可能之前买的
            dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]-prices[i]);
        }
        return Math.max(dp[length-1][0], dp[length-1][1]);
    }
}

4、彩蛋股票问题

题目

现在有一个长度为n的价格数组nums, 表示某只股票每天的价格，你每天最多买入或卖出该只股票的1手股票，买入或者卖出没有手续费，且卖出股票前必须手里已经有股票才能卖出，但是持有的股票数目不受限制，并且初始资金为m元，你在任意时刻都不能进行透支，所以你的资金必须始终大于等于0。请问你在n天结束后，拥有最大的总资产是多少？（总资产：股票数量*股票价格+现金）

输入描述

第一行两个正整数n,m(1<=n<=2000, 1<=m<=10⁹)

第二行n个正整数[a_n](1<=a_i<=10⁹)。其中a_i表示股票在第i天的售价。

输出描述

输出n天结束之后，拥有最大的总资产。

示例1

输入

6 2

2 3 1 1 1 2

输出

6

说明

一种方案是：第一天买入1手股票，第二天卖出1手股票，得到现金3。第三天买入1手股票，第四天买入一手股票，第五天买入一手股票，第六天持有。总共持有3手股票，价格为2，现金为0，总资产为0 + 2*3 = 6。

示例2

输入

3 2

1 1 4

输出

8

说明

一种方案是：第一天买入1手股票，第二天买入1手股票，第三天持有。总共持有2手股票，价格为4，现金为0，总资产为0 + 4*2 = 8。

示例3

输入

4 2

1 1 4 1

输出

5

说明

一种方案是：第一天买入1手股票，第二天买入1手股票，第三天卖出1手股票，第四天持有，总共持有1手股票，价格为1，现金为4，总资产为4 + 1*1 = 5。

示例4

输入

3 100

10 9 8

输出

100

一种方案是：第一天不操作，第二天不操作，第三天持有。总共持有0手股票，价格为8，现金为100，总资产为100 + 0*0 = 100。

解析

1、确定dp数组含义

该题的数组定义借鉴了上一题目。

第i天共有三种状态：买入一支、卖出一支、不操作

定义两个数组：cash[n][3]、stock[n][3]

cash[i][0]：第i天结束后，该天买入一支后的现金数

stock[i][0]：第i天结束后，该天买入一支后的股票数量

以上两个变量共同表示第i天结束后，该天买入一支后的最大收益： cash[i][0]+stock[i][0]*nums[i]

cash[i][1]：第i天结束后，该天卖出一支后的现金数

stock[i][1]：第i天结束后，该天卖出一支后的股票数量

以上两个变量共同表示第i天结束后，该天卖出一支后的最大收益： cash[i][1]+stock[i][1]*nums[i]

cash[i][2]：第i天结束后，该天不操作后的现金数

stock[i][2]：第i天结束后，该天不操作后的股票数量

以上两个变量共同表示第i天结束后，该天卖出一支后的最大收益： cash[i][2]+stock[i][2]*nums[i]

2、状态转移（确定递推公式）

cash[i][0]、stocks[i][0]：

由第一步可知，这两个变量合起来表示该天买入一支股票后的最大资产。我们想在今天买入一支股票，就必须满足第i-1天结束时的现金>=今天的股票价格

那么我们要筛选前一天同时满足以下两种条件那一组：

cash[i-1][x]>=nums[i] (0<=x<=2)
(cash[i-1][x]+stocks[i-1][x]*nums[i])是满足第一个条件中最大的

递推公式为：

如果存在max使得cash[i-1][max]、stocks[i-1][max]满足以上两点：
	cash[i][0] = cash[i-1][max]-nums[i]
	stocks[i][0] = stocks[i-1][max]+1
否则
	cash[i][0] = -2147483648
	stocks[i][0] = -2147483648

cash[i][1]、stocks[i][1]：

这两个变量合起来表示该天必须卖出一支股票后的最大资产。我们想在今天卖出一支股票，就必须满足第i-1天结束时的股票数>=1

那么我们要筛选前一天同时满足以下两种条件那一组：

stocks[i-1][x]>=1 (0<=x<=2)
(cash[i-1][x]+stocks[i-1][x]*nums[i])是满足第一个条件中最大的

递推公式为：

如果存在max使得cash[i-1][max]、stocks[i-1][max]满足以上两点
	cash[i][0] = cash[i-1][max]+nums[i]
	stocks[i][0] = stocks[i-1][max]-1
否则
	cash[i][0] = -2147483648
	stocks[i][0] = -2147483648

cash[i][2]、stocks[i][2]：

这两个变量合起来表示该天不操作后的最大资产。也就是说找到第(i-1)天结束时资产最大的情况对应的cash[i-1][x]和stocks[i-1][x]进行赋值即可。

递推公式为：

cash[i][0] = cash[i-1][max]+nums[i]
stocks[i][0] = stocks[i-1][max]
//（其中cash[i-1][max]，stocks[i-1][max]为资产计算公式(cash[i-1][x]+stocks[i-1][x]*nums[i])计算值最大的那一组）

3、根据递推公式确定dp数组该如何初始化

显而易见，我们需要对cash[0][]和stocks[0][]进行初始化。

if(m >= nums[0]) {
    cash[0][0] = m - nums[0];
    stocks[0][0] = 1;
} else {
	cash[0][0] = 0;
    stocks[0][0] = 0;
}
cash[0][1] = m;
stocks[0][1] = 0;
cash[0][2] = m;
stocks[0][2] = 0;

这里有一个例子来帮助大家理解： alt

4、确定循环遍历顺序

毫无疑问，正序遍历是可以的，我们也没有理由让他倒序遍历。

以下给出具体代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        //输入n、m
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        //输入nums
        int[] nums = new int[n];
        for(int i=0;i<n;i++) {
            nums[i] = scanner.nextInt();
        }

        //创建二维数组，一个存储现金、一个存储股票数
        int[][] stocks = new int[n][3];
        int[][] cash = new int[n][3];
        //定义边界值
        if(m >= nums[0]) {
            cash[0][0] = m - nums[0];
            stocks[0][0] = 1;
        }
        cash[0][1] = m;
        stocks[0][1] = 0;
        cash[0][2] = m;
        stocks[0][2] = 0;

        //开始循环
        for(int i=1;i<n;i++) {
            //买入
            int tempCash = 0, tempStock = 0, sum = Integer.MIN_VALUE;
            for(int j=0;j<3;j++) {
                int tempSum = cash[i-1][j] + stocks[i-1][j] * nums[i];
                if(cash[i-1][j] >= nums[i] && tempSum > sum) {
                    tempCash = cash[i-1][j];
                    tempStock = stocks[i-1][j];
                    sum = tempSum;
                }
                if(tempCash >= nums[i]) {
                    cash[i][0] = tempCash-nums[i];
                    stocks[i][0] = tempStock + 1;
                } else {
                    cash[i][0] = Integer.MIN_VALUE;
                    stocks[i][0] = Integer.MIN_VALUE;
                }
            }
            //卖出
            tempCash = 0;
            tempStock = 0;
            sum = Integer.MIN_VALUE;
            for(int j=0;j<3;j++) {
                int tempSum = cash[i-1][j] + stocks[i-1][j] * nums[i];
                if(stocks[i-1][j] > 0 && tempSum > sum) {
                    tempCash = cash[i-1][j];
                    tempStock = stocks[i-1][j];
                    sum = tempSum;
                }
            }
            if(tempStock > 0) {
                cash[i][1] = tempCash+nums[i];
                stocks[i][1] = tempStock - 1;
            } else {
                cash[i][1] = Integer.MIN_VALUE;
                stocks[i][1] = Integer.MIN_VALUE;
            }
            //不操作
            tempCash = cash[i-1][0];
            tempStock = stocks[i-1][0];
            sum = cash[i-1][0] + stocks[i-1][0] * nums[i];
            for(int j=1;j<3;j++) {
                int tempSum = cash[i-1][j] + stocks[i-1][j] * nums[i];
                if(tempSum > sum) {
                    tempCash = cash[i-1][j];
                    tempStock = stocks[i-1][j];
                    sum = tempSum;
                }
            }
            cash[i][2] = tempCash;
            stocks[i][2] = tempStock;
        }
        int res = cash[n-1][0] + stocks[n-1][0] * nums[n-1];
        for(int i=1;i<3;i++) {
            int temp = cash[n-1][i] + stocks[n-1][i] * nums[n-1];
            if(temp > res)
                res = temp;
        }

        //输出结果
        System.out.println(res);
    }
}