思想

动态规划的核心思想是分治，将复杂问题转换成子问题，通过子问题的迭代逐渐逼近真实问题。
这个过程拆解为：
（1）根据问题寻找状态
（2）定义 dp 数组
（3）明确如何选择，即状态转移方程
（4）明确 base case 和初始值

实例

斐波那切数列 leetcode 509
一个数列由 0 和 1 开始，后面每一项数字都是前面两项数字的和。

状态

这是一个简单示例，问题中没有任何干扰信息，只有数字的值，状态也就是数字的值。

dp 数组

状态是数字的值，dp 数组存储状态即可。
这里要注意的是 dp 数组下标和数字的项的关系。一种方式是二者同步，下标是从 0 开始的，数字的项定义为输入的 n 值，n >= 0。
[0, 1] 是 dp 数组的前两项，代表的含义是输入值 n=0 和 n=1。

状态转移方程

这个问题中方程已经在题目中说明，每一项是前两项之和，即 F(n) = F(n-1) + F(n-2) n>1.
也就是说当输入 n=3 时，F(2) = F(1) + F(0) = 1 + 0 = 1

初始值

边界条件是 F(1) = 1, F(0) = 0

编码

def fib(n: int) -> int:
    # 边界判断
    if n < 0:
        return -1
    # 初始化 dp table，利用 base case
    dp_table = [0] + [1] * n
    # 状态转移方程逐个求解
    for i in range(2, n+1):
        dp_table[i] = dp_table[i-1] + dp_table[i-2]
    # 返回目标值
    return dp_table[n]