概念
通过递归的方式将复杂问题分解成更简单的子问题来简化问题。
动态规划要适用于某个问题，必须具备两个关键属性：最优子结构和重叠子问题。
如果一个问题可以通过组合非重叠子问题的最优解来解决，则该策略称为“分治法”
为了提高效率，我们需要确保每个重叠子问题只计算一次。
最优子结构
如果一个问题的最优解可以由其子问题的最优解构造而成，则称该问题具有最优子结构。这一性质用于确定贪心算法对某个问题的适用性。
通常情况下，如果能够通过归纳法证明贪心算法在每一步都是最优的，则可以使用贪心算法来解决具有最优子结构的问题。
否则，如果问题也存在重叠子问题，则可以使用分治法或动态规划。
如果没有合适的贪心算法，且问题不存在重叠子问题，通常情况下，对解空间进行耗时但直接的搜索是最佳选择。
自下向上
一个问题的解可以用其子问题的解递归地表示出来，并且这些子问题之间存在重叠。
- 先写递归关系
- 从目标问题开始分解
- 用 memo 记录已计算结果
- 适合子问题重复明显的问题
特点为 递归 + 记忆化搜索（memoization）
例：斐波那契数列
F(n)=F(n−1)+F(n−2)
def fib(n, memo={}):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
print(fib(10)) # 55
自下向上
先解决最小的子问题，再逐步推出更大的问题
通常用 循环 + 表格（dp数组）
同样是斐波那契数列
def fib(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fib(10)) # 55