经典动态规划：买卖股票问题

买卖股票的最佳时机: Leetcode 121
买卖股票的最佳时机II: Leetcode 122
买卖股票的最佳时机III: Leetcode 123
买卖股票的最佳时机IV: Leetcode 188
买卖股票的最佳时机含手续费: Leetcode 714
买卖股票的最佳时机含冷冻期: Leetcode 309

动态规划思想

在刷完股票类的动态规划问题之后，对动态规划问题有了新的理解，很多人觉得动态规划问题觉得很难，很正常，包括我也觉得很难，大部分人都会说不知道如何使用动态规划解决，我的理解是：

1. 不知道如何确定dp数组，也就是无法确定状态

2. 不知道如何寻找子结构问题，也就是状态转移方程找不到

而怎么解决这种问题呢？刷题刷题刷题~

许多问题都是有技巧的，掌握了经典的动态规划问题，对解决一般的动态规划问题有很大帮助。

买卖股票问题的解决办法

以最简单的第一题为例，只要掌握了第一题的方法，之后其它问题都只是变形，换汤不换药

LeetCode 121. 买卖股票的最佳时机

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

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
    注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

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

原问题是计算所能获取的最大利润，那么子问题理所当然会想到第i天所能获取的最大利润，你能想到这一点就OK了

② 确定状态并确定数组

接下来要考虑问题拥有什么状态，有n个状态就把定义n维数组

1. 第一个状态：第几天

2. 第二个状态：现在是持有股票还是未持有股票

所以定义二维dp数组：dp[n][2]，[i, j]代表第i天持有股票的状态是j (0代表未持有，1代表持有)，而dp[i][j]代表当前状态的最大利润。

③ 边界状态

边界状态有两个：

1. 第1天没有持有股票（没买入）：dp[0][0] = 0

2. 第1天持有股票（买入）：dp[0][1] = -prices[0]

④ 确定状态转移方程

这一步是最难的，大部分时候解不出来都是因为这一步卡住了，包括我也卡住了，后来参考别人的思路才解出来，所以唯一的办法就是多接触题目，多思考······（多掉头发）

思考前一个状态可以向什么状态转移，转移后的状态得到的利润与前一个状态的利润之间要怎样选择（是更新还是保持原来的值不变）

前一个状态有以下组合方式：

1. 第 i - 1 天未持有股票（dp[i - 1][0]）

2. 第 i - 1 天持有股票（dp[i - 1][1]）

后一个状态有以下组合方式：

1. 第 i 天未持有股票（dp[i][0]）

2. 第 i 天持有股票（dp[i][1]）

所以总共有 2 * 2 = 4种状态转移方式

1. dp[i - 1][0] -----> dp[i][0]   前一天未持有股票，后一天依然未持有股票

2. dp[i - 1][0] -----> dp[i][1]   前一天未持有股票，后一天持有股票（买入股票）

3. dp[i - 1][1] -----> dp[i][0]   前一天持有股票，后一天未持有股票（卖出股票）

4. dp[i - 1][1] -----> dp[i][1]   前一天持有股票，后一天依然持有股票

目标是要取得利润的最大值，所以前一个状态向后一个状态转移时，利润要取最大值，所以得到状态方程：

注意：从dp[i-1][0] -----> dp[i][1]时，利润应该从0开始计算，因为题目要求只能有1次交易（1次买进卖出操作），所以每一次买进时，应该认为之前都没有买进过股票

⑥ 编程实现

 1package leetcode.动态规划.股票问题.买股票的最佳时机;
 2
 3/**
 4 * @author Zeng
 5 * @date 2020/1/21 10:38
 6 */
 7public class Solution {
 8
 9    public static int maxProfit(int[] prices) {
10        if(prices.length == 0){return 0;}
11        int[][] dp = new int[prices.length][2];
12        //边界状态
13        dp[0][0] = 0;
14        dp[0][1] = -prices[0];
15        for(int i = 1; i < prices.length; i++){
16            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
17            dp[i][1] = Math.max(dp[i-1][1], - prices[i]);
18        }
19        return dp_0;
20    }
21
22    public static void main(String[] args) {
23        int[] price = new int[]{7,1,5,3,6,4};
24        int i = maxProfit(price);
25        System.out.println(i);
26    }
27
28}

其它题目也是按照相同的思想进行解决，只是在第一题的基础上加上一些额外的条件。