适合用Dynamic Program解决的问题，存在着状态传递。

将递归过程中的状态存储起来，用于推导后续状态就是动态规划。

基础概念

动态规划的本质就是对中间状态进行保存，对子问题的解答结果进行保存，自底向上解出许多子问题，然后再做出选择，往往每一个步骤都求做一个选择，这个选择往往依赖于之前子问题的解。递归（分而治之）加上状态记录，利用记忆状态，避免重复判断，就是动态规划。

简而言之，动态规划是从上往下分析问题，从下往上求解问题。

动态规划、DFS、回溯、递归之间的关系？

递归是DFS（深度优先搜索）的一种实现方式，DFS是动态规划的一种实现方式。回溯法是DFS过程中可以进行的可选操作。动态规划 > DFS(回溯法) > 递归

哪些问题可以用动态规划解决？

满足以下四个条件的问题可以考虑用动态规划解决：

1. 该问题要求最优解。
2. 整体问题的最优解是依赖各个子问题的最优解。
3. 子问题之间还有相互重叠的更小的子问题。
4. 该问题适用于从上往下分析问题，从下往上求解问题的 解决思路。

那怎么知道它就存在「重叠子问题」呢，这似乎不容易看出来？

解答这个问题，最直观的应该是随便假设一个输入，然后画递归树，肯定是可以发现相同节点的。这属于定量分析，其实不用这么麻烦，下面我来教你定性分析，一眼就能看出「重叠子问题」性质。拿最简单的斐波那契数列举例：

def func(n):
    # 给递归一个出口  第一位和第二位都是1
    if n == 1 or n == 2:
        return 1
    else:
        # 从第三位开始  返回上一个数加上上一个数
        return func(n-1) + func(n-2)

我们抽象出递归算法的框架：

def fib(n):
    fib(n - 1)
    fib(n - 2)

看着这个框架，请问原问题 \(f(n)\)，如何触达子问题 \(f(n - 2)\)？有两种路径，

一是 \[ f(n) -> f(n-1) -> f(n - 1 - 1) \] 二是 \[ f(n) -> f(n - 2) \] 前者经过两次递归，后者进过一次递归而已。两条不同的计算路径都到达了同一个问题，这就是「重叠子问题」，而且可以肯定的是，只要你发现一条重复路径，这样的重复路径一定存在千万条，意味着巨量子问题重叠。

代码实现过程

直接入手（简单问题）

以 剑指offer 面试题47. 礼物的最大价值（中） 为例： 1、状态定义：设函数 \(f(i, j)\) 为到达坐标 \((i, j)\) 能拿到的礼物总和的最大值。 2、转移方程确定：由题意可知，通过 \((i,j-1)\) 和 \((i-1, j)\) 都可以达到 \((i, j)\)。则状态转移方程为：\(f(i, j) = max(f(i, j-1), f(i-1, j)) + gift(i, j)\)。其中，\(gift(i,j)\) 为坐标\((i, j)\)的格子里礼物的价值。

曲线救国（复杂问题）

1、将原问题用递归实现（可以用到回溯法） 2、添加保存（记忆）状态的变量，将递归代码写入dp函数。

动态规划算法框架

mono = {}  # 声明记忆状态的变量
def dp(指定状态的参数):
	# 判断该状态是否处理过，如果处理过，就直接返回
	if memo中保存了该状态:
		return mono中该状态的保存结果
	# 针对该状态的递归代码
	if ...:
		... # 更新指定状态的参数
		ans = dp(指定状态的参数)
	else:
		... # 更新指定状态的参数
		ans = dp(指定状态的参数)
	
	mono[指定状态的参数作为dict的key] = ans  # 将这个未添加的状态添加到mono钟
	return ans

状态转移方程

求解动态规划问题过程中，理清楚状态转移方程至关重要，基于状态转移方程才能将前面记忆的结果用于后面状态的计算。

• 以斐波 那契数列举例，我们知道当前求解的数，是前面一个数和前前面一个数的和，所以状态转移方程如下： \[ f(n) = f(n - 1) + f(n - 2) \]
• 以LeetCode 62. 不同路径为例，由于只能水平向右和竖直向下行进，所以达到当前位置的可能路径条数，只能是达到右边位置的路径条数和到达上边位置的路径条数之和，所以状态转移方程如下：
  \[ dp[i][j] = dp[i-1][j] * dp[i][j-1] \]

有了状态转移方程，将过去的状态根据题意，以 list 或者 matrix 的形式保存，持续更新，就能得到最终的结果了。注意初始状态的更新方法。

关键思想总结

关于动态规划的模板算法，可以参看 动态规划套路秒杀背包问题 这篇文章。

相关LeetCode题目

LeetCode 10. 正则表达式匹配（难）

直觉

这个题目，递归回溯实现比较复杂，用动态规划更简单。这道题也是剑指offer原题，值得推荐，从递归到到动态规划，逐层递进，需要多学习，多复习。

关键代码

class Solution(object):
    def isMatch(self, text, pattern):
        if not pattern:
            return not text

        first_match = bool(text) and pattern[0] in {text[0], '.'}

        if len(pattern) >= 2 and pattern[1] == '*':
            res = (
                self.isMatch(text, pattern[2:])
                or
                (first_match and self.isMatch(text[1:], pattern))
            )
            return res
        else:
            return first_match and self.isMatch(text[1: ], pattern[1: ])

        
class Solution(object):
    def isMatch(self, text, pattern):
        memo = dict()
        def dp(i, j):
            if (i, j) in memo:  return memo[(i, j)]
            if j == len(pattern):  return i == len(text)
            first_match = i < len(text) and pattern[j] in {text[i], '.'}

            if j <= len(pattern) - 2 and pattern[j + 1] == '*':
                ans = dp(i, j+2) or first_match and dp(i+1, j)
            else:
                ans = first_match and dp(i+1, j+1)
            
            memo[(i, j)] = ans
            return ans
        return dp(0, 0 )

题解

LeetCode-10-正则表达式匹配（难）

LeetCode 64. 最小路径和（中）

直觉

关键代码

题解

LeetCode 64. 最小路径和（中）

LeetCode 70. 爬楼梯（易）

直觉

计算从第一层到达每一层可能的N方法，一直叠加。动态规划的状态转移公式为： dp[n] = dp[n-1] + dp[n-2]。

关键代码

def func(n):
    dp = [0] * n
    if n < 3:  return n
	dp[0], dp[1] = 1, 2 
    for i in range(2, n):
        dp[n] = dp[n-2] + dp[n-1] 
return dp[-1]

题解

LeetCode 70. 爬楼梯（易）

LeetCode 89. 格雷编码（中）

题目

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。 给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

直觉

1、先翻转 0 1，得到长度为 n 的排列 0 1 1 0 （n=4）。
2、在前 n/2 个数字不变，在后 n/2 个排列前加 1。组成新排列，以此类推。

这个解法也可以理解成动态规划，状态转移方程就是：

dp[j] += dp[j-1] | 1 << i

关键代码

class Solution:
    def grayCode(self, n: int) -> List[int]:
        res = [0]
        for i in range(n):
            size = len(res)
            # 为啥要从后面往前循环，因为是镜像的，由0 1得到1 0，所以必须从后往前循环。
            for j in range(size-1, -1, -1):
                res.append(res[j] | (1 << i))
        return res

题解

LeetCode 89. 格雷编码（中）

LeetCode 97. 交错字符串（难）

题目

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

直觉

设立一个表示进位的变量carried，建立一个新链表，把输入的两个链表从头往后同时处理，每两个相加，将结果加上carried后的值作为一个新节点到新链表后面。

关键代码

题解

LeetCode 97. 交错字符串（难）