终于到经典的动态规划问题，希望能顺利拿下。

动态规划

入门

首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离等等。

既然是要求最值，求解动态规划的核心问题是穷举**。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。

动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因。

提供一个思维框架，辅助思考状态转移方程：

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

斐波那契数列

PS：但凡遇到需要递归的问题，最好都画出递归树，这对分析算法的复杂度，寻找算法低效的原因都有巨大帮助。

这个递归树怎么理解？就是说想要计算原问题 f(20)，我就得先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，我就要先算出子问题 f(18) 和 f(17)，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。

递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。

首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。

然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。

所以，这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别，爆炸。

观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如 f(18) 被计算了两次，而且你可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 f(18) 这一个节点被重复计算，所以这个算法及其低效。

这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。

带备忘录的递归

明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。

实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。

子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。

解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。

所以，本算法的时间复杂度是 O(n)。比起暴力算法，是降维打击。

至此，带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。

啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。

啥叫「自底向上」？反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

DP 数组的迭代解法

有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算岂不美哉！

画个图就很好理解了，而且你发现这个 DP table 特别像之前那个「剪枝」后的结果，只是反过来算而已。实际上，带备忘录的递归解法中的「备忘录」，最终完成后就是这个 DP table，所以说这两种解法其实是差不多的，大部分情况下，效率也基本相同。

这里，引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：

为啥叫「状态转移方程」？其实就是为了听起来高端。你把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移，仅此而已。

你会发现，上面的几种解法中的所有操作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性，它是解决问题的核心。而且很容易发现，其实状态转移方程直接代表着暴力解法。

千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。只要写出暴力解，优化方法无非是用备忘录或者 DP table，再无奥妙可言。

这个例子的最后，讲一个细节优化。细心的读者会发现，根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：

int fib(int n) {
    if (n == 2 || n == 1) 
        return 1;
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

这个技巧就是所谓的「状态压缩」，如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据，上述例子就相当于把DP table 的大小从 n 缩小到 2。后续的动态规划章节中我们还会看到这样的例子，一般来说是把一个二维的 DP table 压缩成一维，即把空间复杂度从 O(n^2) 压缩到 O(n)。

有人会问，动态规划的另一个重要特性「最优子结构」，怎么没有涉及？下面会涉及。斐波那契数列的例子严格来说不算动态规划，因为没有涉及求最值，以上旨在说明重叠子问题的消除方法，演示得到最优解法逐步求精的过程。下面，看第二个例子，凑零钱问题。

凑零钱问题

上面的斐波那契数列很好理解，这个凑零钱问题，理解难度也并不是很高，但是这个凑零钱问题的代码如果直接接触的话会有点难度。

先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。

那么那么首先理一下思路，递归的思路如下，我们在这使用递归先解一遍。

public class Coin2 {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 100;

        System.out.println(System.currentTimeMillis());
        int count = new Coin2().coinChange(coins, amount);
        System.out.println(System.currentTimeMillis());
        System.out.println(count);
    }

    int res = Integer.MAX_VALUE;

    private int coinChange(int[] coins, int amount) {
        if (coins.length == 0) {
            return -1;
        }
        helper(coins, amount, 0);
        if (res == Integer.MAX_VALUE) {
            return -1;
        }
        return res;
    }

    private void helper(int[] coins, int amount, int count) {
        if (amount < 0) {
            return;
        }

        if (amount == 0) {
            res = Math.min(res, count);
        }

        for (int i = 0; i < coins.length; i++) {
            helper(coins, amount - coins[i], count + 1);
        }
    }
}

这样解有个很大的问题，很明显的，这里的时间复杂度已经到了令人无法接受的程度，用时非常非常久。

int[] coins = {1, 2, 5};
int amount = 100;

如果用100来试最小硬币的耗时已经到了使用小时为单位的程度。

为了优化，接下来使用记忆化递归。

我们对其进行优化，进行记忆化递归，记忆化递归就是将已运算的结果进行存储，如上图我们对剩9元进行存储，在下次遍历到剩9元硬币时就可以直接返回结果，不必再次遍历。

package leecode;

/**
 * @Author Fly.Hugh
 * @Date 2020/9/11 11:26
 * @Version 1.0
 **/
public class Coin3 {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 1000;

        System.out.println(System.currentTimeMillis());
        int count = new Coin3().coinChange(coins, amount);
        System.out.println(System.currentTimeMillis());
        System.out.println(count);
    }

    public int coinChange(int[] coins, int amount) {
        if (amount < 1) return 0;
        return helper(coins, amount, new int[amount]);
    }

    public int helper(int[] coins, int amount, int[] res) {
        if (amount < 0) {
            return -1;
        }

        if (amount == 0) return 0;

        if (res[amount - 1] != 0) {
            return res[amount - 1];
        }

        int min = Integer.MAX_VALUE;
        
        for (int i = 0; i < coins.length; i++) {
            int ress = helper(coins, amount - coins[i], res);
            if (ress >= 0 && ress < min) {
                min = ress + 1;
            }
        }

        res[amount - 1] = min == Integer.MAX_VALUE ? -1 : min;
        System.out.println("index = " + (amount-1) + "的时候，值是"+ res[amount - 1] );

        return res[amount - 1];
    }
}

这里面最重要的代码

for (int i = 0; i < coins.length; i++) {
    int ress = helper(coins, amount - coins[i], res);
    if (ress >= 0 && ress < min) {
        min = ress + 1;
    }
}

下面是状态转移方程

只要用这个方程的角度来理解这个代码就很好理解，

外面一层For是用来遍历coins的，然后里面就是递归到最后求值，整个程序的执行结果

C:\Env\jdk1.8.0_144\bin\java.exe "-javaagent:C:\App\IntelliJ IDEA 
index = 0的时候，值是1
index = 1的时候，值是1
index = 2的时候，值是2
index = 3的时候，值是2
index = 4的时候，值是1
index = 5的时候，值是2
index = 6的时候，值是2
index = 7的时候，值是3
index = 8的时候，值是3
index = 9的时候，值是2
index = 10的时候，值是3
1599804625398
200

Process finished with exit code 0

整个程序从最里面，amount最小的值开始往字典上面记录，然后到最后结束。

下面第三种解法，动态规划解法。

动态规划解法也就是自底向上，动态规划就是将前面计算的结果拿来给后面用，因此如何定义就是一个问题，在这个问题中，我们定义数组res【amount+1】，数组代表数组下标对应的硬币元数所需的最小个数的合集。

package leecode;

import java.util.Arrays;

/**
 * @Author Fly.Hugh
 * @Date 2020/9/11 14:37
 * @Version 1.0
 **/
public class Coin4 {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;

        int count = new Coin4().coinChange(coins, amount);
        System.out.println(count);
    }

    public int coinChange(int[] coins, int amount) {
        //  对于题意，对于任意给出的数来说，需要的硬币数量 > 这个数本身必定是最大值
        int max = amount + 1;
        //  dp的函含义是     对于每个index为amount的钱，value总是其需要的最小硬币数量、
        int[] dp = new int[amount + 1];
        //  对dp的每个值进行填充
        Arrays.fill(dp, max);
        //  0元需要0个硬币来兑换
        dp[0] = 0;
        //  外层是 amount的遍历，从1开始
        for (int i = 1; i <= amount; i++) {
            // 内层遍历的是 硬币的种类
            for (int j = 0; j < coins.length; j++) {
                /** 这个判断要思考一下，比如说  i = 1的时候，
                 *  coins[j] 前后分别是 1，2，5
                 *  如果coins <= j 的时候也就是说，当硬币面额小于余额的时候才会判断。
                 *  这个时候读取了 dp[0]的值，dp[1] = dp[0] + 1
                 *
                 *  当数组比较大(大于最大值的硬币)的时候，这个判断有点类似于没用了，
                 *  后面进行的的判断，会把dp[i]中每个硬币的组合都判断一遍。同时更新到了数组里面，取最小值
                 * */
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        //  最后返回了数组。
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

到这个时候本文仅仅引入了状态转移方程这一个概念，下面从动态规划的角度讲一下这题。

这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？用一个直观的例子来讲解。

比如说，假设你考试，每门科目的成绩都是互相独立的。你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。

得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，“每门科目考到最高”这些子问题是互相独立，互不干扰的。

但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，数学分数高，语文分数就会降低，反之亦然。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。

回到凑零钱问题，为什么说它符合最优子结构呢？比如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。

PS：关于最优子结构的问题，后文还会再举例探讨。

那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？

1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数：

dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。

搞清楚上面这几个关键点，解法的伪码就可以写出来了：

# 伪码框架
def coinChange(coins: List[int], amount: int):

    # 定义：要凑出金额 n，至少要 dp(n) 个硬币
    def dp(n):
        # 做选择，选择需要硬币最少的那个结果
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res

    # 题目要求的最终结果是 dp(amount)
    return dp(amount)

根据伪码，我们加上 base case 即可得到最终的答案。显然目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1：

def coinChange(coins: List[int], amount: int):

    def dp(n):
        # base case
        if n == 0: return 0
        if n < 0: return -1
        # 求最小值，所以初始化为正无穷
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            # 子问题无解，跳过
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)

        return res if res != float('INF') else -1

    return dp(amount)

至此，状态转移方程其实已经完成了，以上算法已经是暴力解法了，以上代码的数学形式就是状态转移方程：

递归算法的时间复杂度分析：子问题总数 x 每个子问题的时间。

子问题总数为递归树节点个数，这个比较难看出来，是 O(n^k)，总之是指数级别的。每个子问题中含有一个 for 循环，复杂度为 O(k)。所以总时间复杂度为 O(k * n^k)，指数级别。

2、带备忘录的递归

类似之前斐波那契数列的例子，只需要稍加修改，就可以通过备忘录消除子问题：

def coinChange(coins: List[int], amount: int):
    # 备忘录
    memo = dict()
    def dp(n):
        # 查备忘录，避免重复计算
        if n in memo: return memo[n]
        # base case
        if n == 0: return 0
        if n < 0: return -1
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)

        # 记入备忘录
        memo[n] = res if res != float('INF') else -1
        return memo[n]

    return dp(amount)

不画图了，很显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。

3、dp 数组的迭代解法

当然，我们也可以自底向上使用 dp table 来消除重叠子问题，关于「状态」「选择」和 base case 与之前没有区别，dp 数组的定义和刚才 dp 函数类似，也是把「状态」，也就是目标金额作为变量。不过 dp 函数体现在函数参数，而 dp 数组体现在数组索引：

dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。

根据我们文章开头给出的动态规划代码框架可以写出如下解法：

int coinChange(vector<int>& coins, int amount) {
    // 数组大小为 amount + 1，初始值也为 amount + 1
    vector<int> dp(amount + 1, amount + 1);
    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.size(); i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            if (i - coin < 0) continue;
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

PS：为啥 dp 数组初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。

第一个斐波那契数列的问题，解释了如何通过「备忘录」或者「dp table」的方法来优化递归树，并且明确了这两种方法本质上是一样的，只是自顶向下和自底向上的不同而已。

第二个凑零钱的问题，展示了如何流程化确定「状态转移方程」，只要通过状态转移方程写出暴力递归解，剩下的也就是优化递归树，消除重叠子问题而已。

如果你不太了解动态规划，还能看到这里，真得给你鼓掌，相信你已经掌握了这个算法的设计技巧。

计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。

列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。

备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门，除此之外，试问，还能玩出啥花活？

之后我们会有一章专门讲解动态规划问题，如果有任何问题都可以随时回来重读本文，希望读者在阅读每个题目和解法时，多往「状态」和「选择」上靠，才能对这套框架产生自己的理解，运用自如。

Tips

下面主要讲两个常见问题：

1、到底什么才叫「最优子结构」，和动态规划什么关系。

2、为什么动态规划遍历dp数组的方式五花八门，有的正着遍历，有的倒着遍历，有的斜着遍历，有的无论咋遍历都是对的。

一、最优子结构详解

「最优子结构」是某些问题的一种特定性质，并不是动态规划问题专有的。也就是说，很多问题其实都具有最优子结构，只是其中大部分不具有重叠子问题，所以我们不把它们归为动态规划系列问题而已。

我先举个很容易理解的例子：假设你们学校有 10 个班，你已经计算出了每个班的最高考试成绩。那么现在我要求你计算全校最高的成绩，你会不会算？当然会，而且你不用重新遍历全校学生的分数进行比较，而是只要在这 10 个最高成绩中取最大的就是全校的最高成绩。

这个问题就符合最优子结构：可以从子问题的最优结果推出更大规模问题的最优结果。让你算每个班的最优成绩就是子问题，你知道所有子问题的答案后，就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。

你看，这么简单的问题都有最优子结构性质，只是因为显然没有重叠子问题，所以我们简单地求最值肯定用不出动态规划。

再举个例子：假设你们学校有 10 个班，你已知每个班的最大分数差（最高分和最低分的差值）。那么现在我让你计算全校学生中的最大分数差，你会不会算？可以想办法算，但是肯定不能通过已知的这 10 个班的最大分数差推到出来。因为这 10 个班的最大分数差不一定就包含全校学生的最大分数差，比如全校的最大分数差可能是 3 班的最高分和 6 班的最低分之差。

这次我给你提出的问题就不符合最优子结构，因为你没办通过每个班的最优值推出全校的最优值，没办法通过子问题的最优值推出规模更大的问题的最优值。

想满足最优子结，子问题之间必须互相独立。全校的最大分数差可能出现在两个班之间，显然子问题不独立，所以这个问题本身不符合最优子结构。

那么遇到这种最优子结构失效情况，怎么办？策略是：改造问题。对于最大分数差这个问题，我们不是没办法利用已知的每个班的分数差吗，那我只能这样写一段暴力代码：

int result = 0;
for (Student a : school) {
    for (Student b : school) {
        if (a is b) continue;
        result = max(result, |a.score - b.score|);
    }
}
return result;

改造问题，也就是把问题等价转化：最大分数差，不就等价于最高分数和最低分数的差么，那不就是要求最高和最低分数么，不就是我们讨论的第一个问题么，不就具有最优子结构了么？那现在改变思路，借助最优子结构解决最值问题，再回过头解决最大分数差问题，是不是就高效多了？

当然，上面这个例子太简单了，不过请读者回顾一下，我们做动态规划问题，是不是一直在求各种最值，本质跟我们举的例子没啥区别，无非需要处理一下重叠子问题。

再举个常见但也十分简单的例子，求一棵二叉树的最大值，不难吧（简单起见，假设节点中的值都是非负数）：

int maxVal(TreeNode root) {
    if (root == null)
        return -1;
    int left = maxVal(root.left);
    int right = maxVal(root.right);
    return max(root.val, left, right);
}

你看这个问题也符合最优子结构，以root为根的树的最大值，可以通过两边子树（子问题）的最大值推导出来，结合刚才学校和班级的例子，很容易理解吧。

当然这也不是动态规划问题，旨在说明，最优子结构并不是动态规划独有的一种性质，能求最值的问题大部分都具有这个性质；

但反过来，最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的，以后碰到那种恶心人的最值题，思路往动态规划想就对了，这就是套路。

动态规划不就是从最简单的 base case 往后推导吗，可以想象成一个链式反应，不断以小博大。但只有符合最优子结构的问题，才有发生这种链式反应的性质。

找最优子结构的过程，其实就是证明状态转移方程正确性的过程，方程符合最优子结构就可以写暴力解了，写出暴力解就可以看出有没有重叠子问题了，有则优化，无则 OK。这也是套路。

二、dp 数组的遍历方向

做动态规划问题时，肯定会对dp数组的遍历顺序有些头疼。我们拿二维dp数组来举例，有时候我们是正向遍历：

int[][] dp = new int[m][n];
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        // 计算 dp[i][j]

有时候我们反向遍历：

for (int i = m - 1; i >= 0; i--)
    for (int j = n - 1; j >= 0; j--)
        // 计算 dp[i][j]

有时候可能会斜向遍历：

// 斜着遍历数组
for (int l = 2; l <= n; l++) {
    for (int i = 0; i <= n - l; i++) {
        int j = l + i - 1;
        // 计算 dp[i][j]
    }
}

甚至更让人迷惑的是，有时候发现正向反向遍历都可以得到正确答案，比如我们在 团灭 LeetCode 股票买卖问题 中有的地方就正反皆可。

如果仔细观察的话可以发现其中的原因的:

1、遍历的过程中，所需的状态必须是已经计算出来的。

2、遍历的终点必须是存储结果的那个位置。

下面来具体解释上面两个原则是什么意思。

比如编辑距离这个经典的问题，详解见前文 经典动态规划：编辑距离，我们通过对dp数组的定义，确定了 base case 是dp[..][0]和dp[0][..]，最终答案是dp[m][n]；而且我们通过状态转移方程知道dp[i][j]需要从dp[i-1][j],dp[i][j-1],dp[i-1][j-1]转移而来，如下图：

那么，参考刚才说的两条原则，你该怎么遍历dp数组？肯定是正向遍历：

for (int i = 1; i < m; i++)
    for (int j = 1; j < n; j++)
        // 通过 dp[i-1][j], dp[i][j - 1], dp[i-1][j-1]
        // 计算 dp[i][j]

因为，这样每一步迭代的左边、上边、左上边的位置都是 base case 或者之前计算过的，而且最终结束在我们想要的答案dp[m][n]。

再举一例，回文子序列问题，详见前文 子序列解题模板：最长回文子序列，我们通过过对dp数组的定义，确定了 base case 处在中间的对角线，dp[i][j]需要从dp[i+1][j],dp[i][j-1],dp[i+1][j-1]转移而来，想要求的最终答案是dp[0][n-1]，如下图：

这种情况根据刚才的两个原则，就可以有两种正确的遍历方式：

要么从左至右斜着遍历，要么从下向上从左到右遍历，这样才能保证每次dp[i][j]的左边、下边、左下边已经计算完毕，最终得到正确结果。

现在，你应该理解了这两个原则，主要就是看 base case 和最终结果的存储位置，保证遍历过程中使用的数据都是计算完毕的就行，有时候确实存在多种方法可以得到正确答案，可根据个人口味自行选择。

动态规划设计：正则表达式

需求：给定一个字符串 (s) 和一个字符模式 ( p)。实现支持 . 和 * 的正则表达式匹配。

• . 匹配任意单个字符。
• * 匹配零个或多个前面的元素。

匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例：

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

来自LeetCode第10题

题意：

• 这道题中的*表示之前那个字符可以有0个，1个或是多个，就是说，字符串"a*b"，可以表示"b"或是"aaab"，即a的个数任意（可以是0个，可以是3个），可以从示例4看出。
• 还有一个需要注意的点就是 ".*" 表示可匹配零个或多个('*')任意字符('.')，示例3

'*'这个字符，它能表示前一个字符的 0~n 个副本。说到这里，我们就要将一个编程中经常提到的概念，自动机。

状态机由状态寄存器和组合逻辑电路构成，能够根据控制信号按照预先设定的状态进行状态转移，是协调相关信号动作、完成特定操作的控制中心。有限状态机简写为FSM(Finite State Machine)

有些地方也把状态机称为有限自动机

解决正则表达问题的关键，在于我们如何构建一个合适的自动机

然后此题又是一个非确定状态有限自动机，要自己手动构建一个，这种接法姑且搁置，后面阅读FlinkCEP源码的时候我再来分析。

---

所以这里：

从头处理s和p两个字符串：

• 首先，如果p为空了，此时若s不为空，则说明匹配失败，直接返回false，如果都为空，说明匹配结束，返回true。

• 其次，如果p不为空，存在两种情况，一种是单一匹配，一种是'*'的任意匹配。

  • 我们先假设单一匹配，创建一个boolean类型的match变量，计算一下单一匹配是否成功：

    • 在单一匹配的情况下，s*不能为空。
    • s和p的当前第一个字符需要相等，或者p的第一个字符为'.'。

    如果成功就可以将两个字符串的第一位去掉，继续匹配后续的字符。

  • 还有可能是要进行任意匹配，任意匹配的条件是当前p的长度要大于2，并且p[1]要为'*'，这个时候，可以匹配s中任意数量的字符p[0]。那么又是两种情况：

    • 看：如果看（匹配）一次，就相当于去掉s的第一个字符，继续向后匹配。

    • 不看：如果不看（就是不进行匹配=匹配0次），就相当于s不变，p向后去掉两位（字符p[0]和p[1]的’*‘）。

class Solution {
    public boolean isMatch(String s, String p) {
        if(p.isEmpty()) return s.isEmpty();
        // *不代表0的匹配条件
        boolean match = !s.isEmpty() && ((s.charAt(0) == p.charAt(0)) || p.charAt(0) == '.');
        // 任意匹配
        if(p.length() >= 2 && p.charAt(1) == '*') return isMatch(s, p.substring(2)) || (match && isMatch(s.substring(1), p));
        // 单一匹配
        return match && isMatch(s.substring(1), p.substring(1));
    }
}

tips: 这里有个点要注意，通过charAt的方式访问要比char[]的方式慢很多，作为对比，这里附上通过toCharArray转换的版本，前者用时109ms，后者17ms，可见差距之大。这里主要应该是因为charAt方法多了一层栈的深度（需要进出对象）。

class Solution {
    public boolean isMatchChar(char[] s, int s1, char[] p, int p1) {
        if(p1 >= p.length) return s1 >= s.length;
        boolean match = s1 < s.length && ((s[s1] == p[p1]) || p[p1] == '.');
        if(p.length - p1 >= 2 && p[p1 + 1] == '*') return isMatchChar(s, s1, p, p1 + 2) || (match && isMatchChar(s, s1 + 1, p, p1));
        return match && isMatchChar(s, s1 + 1, p, p1 + 1);
    }
    
    public boolean isMatch(String s, String p) {
        char[] ss = s.toCharArray(), pp = p.toCharArray();
        return isMatchChar(ss, 0, pp, 0);
    }
}

记忆化递归

int[][] mem;
public boolean isMatchChar(char[] s, int s1, char[] p, int p1) {

    if(p1 >= p.length) return s1 >= s.length;
    if(mem[s1][p1] != 0) return mem[s1][p1] > 0;

    boolean match = s1 < s.length && ((s[s1] == p[p1]) || p[p1] == '.');

    if(p.length - p1 >= 2 && p[p1 + 1] == '*') {
        boolean t = isMatchChar(s, s1, p, p1 + 2) || (match && isMatchChar(s, s1 + 1, p, p1));
        if(t) mem[s1][p1] = 1;
        else mem[s1][p1] = -1;
        return t;
    }
    
    boolean t = match && isMatchChar(s, s1 + 1, p, p1 + 1);
    if(t) mem[s1][p1] = 1;
    else mem[s1][p1] = -1;
    return t;
}

public boolean isMatch(String s, String p) {
    this.mem = new int[s.length() + 1][p.length() + 1];
    char[] ss = s.toCharArray(), pp = p.toCharArray();
    return isMatchChar(ss, 0, pp, 0);
}

这段就是记忆化递归的套路

   this.mem = new int[s.length() + 1][p.length() + 1];

if(mem[s1][p1] != 0) return mem[s1][p1] > 0;

if(t) mem[s1][p1] = 1;
   else mem[s1][p1] = -1;

动态规划

s和p倒着看，dp[i][j]的取值分为以下几种情况：
1.p[j - 1]p[j−1]为普通字符,若s[i - 1] == p[j - 1]，则dp[i][j] = dp[i - 1][j - 1]，否则匹配失败
							两个Char数组相同				那么dp表中
2.p[j−1]为'.'，则dp[i][j] = dp[i - 1][j - 1]

3.p[j - 1]p[j−1]为'*'：
	(1)不看，则dp[i][j] = dp[i][j - 2]
	(2)看，则dp[i][j] = dp[i - 1][j]

public boolean isMatch_DP(String s, String p) {
    char[] str = s.toCharArray(), ptr = p.toCharArray();
    boolean[][] dp = new boolean[str.length + 1][ptr.length + 1];
    dp[0][0] = true;
    for (int i = 0; i <= str.length; i++) {
        for (int j = 1; j <= ptr.length; j++) {
            if(ptr[j - 1] != '*') {
                if(i > 0 && (str[i - 1] == ptr[j - 1] || ptr[j - 1] == '.')) dp[i][j] = dp[i - 1][j - 1];
            }else { //ptr[j - 1] == '*'
                if(j > 1) dp[i][j] |= dp[i][j - 2];   //不看
                if(i > 0 && j > 1 && (str[i - 1] == ptr[j - 2] || ptr[j - 2] == '.'))dp[i][j] |= dp[i - 1][j];    //看
            }
        }
    }
    return dp[str.length][ptr.length];
}