从子问题解决原问题，动态规划一般有自顶向下和自底向上两种编写方式
Bottom-Up
自底向上 (Bottom-Up)，形式上对应迭代 (iteration)：巧妙地安排求解顺序，从最小的子问题开始利用循环逐步计算并将结果存在 dp 数组里，基于子问题的结果向后计算。
以计算斐波那契数列的第 n 个数为例，普通循环结构的求解方式如下：
2
3
4
5
6
7
8
9
a = 0
b = 1
if n == 1: return a
if n == 2: return b
# 迭代步骤
for i in range(2, n):
a, b = b, a+b
return b时间复杂度为一次循环的 \(O(n)\)；空间复杂度为常数变量的 \(O(1)\)。
使用自底向上的动态规划编写方式如下：
2
3
4
5
6
7
# dp 数组
fib = [0, 1]
# 自底向上，基于之前的结果逐步向后计算
for i in range(2, n):
fib.append(fib[i-1] + fib[i-2])
return fib[n-1]时间复杂度为一次循环的 \(O(n)\)；空间复杂度为 dp 数组消耗的 \(O(n)\)。
Top-Down
自顶向下 (Top-Down)，形式上对应递归 (recursion)，也被称为记忆化搜索：这种写法利用函数调用自身来求解，只有当子问题的递归返回结果，原问题才能求解（如果调用过程中不存储上一个状态的解，就是普通递归；如果储存了上一个状态的解，就是自顶向下的动态规划）。
- 相较于自底向上的优点：代码将会十分简洁，并且不需要考虑很多特殊情况和边界条件，这是因为「记忆化搜索」只会「搜索」可行的状态；
- 相较于普通递归的优点：以空间换时间，通过使用额外的 dp 数组储存之前的解，来减少递归调用的次数；
以计算斐波那契数列的第 n 个数为例，普通递归结构的求解方式如下：
2
3
4
5
if n == 1: return 0
if n == 2: return 1
# 递归步骤
return Fibonacci(n-1) + Fibonacci(n-2)函数每次递归，都至少需要调用两次它本身，时间复杂度可以从以下两个角度计算：
假设时间复杂度为 \(T(n)\)，则有：\(T(n) = T(n-1) + T(n-2)\)，这其实就是斐波那契数列本身的递推式，根据斐波那契数列的通项公式，\(T(n)\) 应该不超过通项公式的最大次项，即 \(T(n) \in O\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}\right)\)，即时间复杂度约为 \(O(2^n)\)；
如果将每次调用函数看做一个节点，则可以画出一个以
Fibonacci(n)为根，叶节点全部为Fibonacci(0)和Fibonacci(1)，高为 \(n\) 的二叉树，显然该二叉树的节点个数就是调用次数，而高为 \(n\) 的满二叉树的节点个数为 \(2^n - 1\)，因此时间复杂度为 \(O(2^n)\)；> graph TB; A["Fibonacci(5)"] --- B["Fibonacci(4)"] & C["Fibonacci(3)"]; B --- D["Fibonacci(3)"] & E["Fibonacci(2)"]; C --- F["Fibonacci(2)"] & G["Fibonacci(1)"]; D --- H["Fibonacci(2)"] & I["Fibonacci(1)"]; H --- J["Fibonacci(1)"] & K["Fibonacci(0)"]; E --- L["Fibonacci(1)"] & M["Fibonacci(0)"]; F --- N["Fibonacci(1)"] & O["Fibonacci(0)"];空间复杂度为常数变量的 \(O(1)\)。
自顶向下的动态规划编写方式如下：
2
3
4
5
6
7
8
9
10
11
12
13
# dp 数组，-1 表示未计算的位置
fib = [-1] * n
# 递归函数
def rec(n, fib):
if n == 1: return 0
if n == 2: return 1
# 递归步骤：仅在动态规划数组中未计算的位置调用函数本身
if fib[n-1] == -1: # 仅当第 n 个位置还未被计算时，才进行递归
fib[n-1] = rec(n-1) + rec(n-2)
return fib[n-1]由于对 dp 数组的每个位置只计算了一次
Fibonacci()，舍弃了重复计算，因此时间复杂度为 \(O(n)\)；空间复杂度为 dp 数组消耗的 \(O(n)\)。