动态规划

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

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

斐波那契数列

function fib(n) {
    if (n === 1 || n === 2) return 1;
    return fib(n - 1) + fib(n - 2);
}
// O(2-n)

重叠子问题

增加备忘录

function  fib(n) {
    // 备忘录全初始化为 0
    let meno = []
    // 进行带备忘录的递归
    return helper(memo, n);
}

function helper(memo, n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过，不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}


// O(n)

状态转移

自底向上

int fib(int N) {
    if (N == 0) return 0;
    let dp = []
    // base case
    dp[0] = 0; dp[1] = 1;
    // 状态转移
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[N];
}

进一步优化

int fib(int n) {
    if (n == 0 || n == 1) {
        // base case
        return n;
    }
    // 分别代表 dp[i - 1] 和 dp[i - 2]
    int dp_i_1 = 1, dp_i_2 = 0;
    for (int i = 2; i <= n; i++) {
        // dp[i] = dp[i - 1] + dp[i - 2];
        int dp_i = dp_i_1 + dp_i_2; // DP table 的大小从 n 缩小到 2
        // 滚动更新
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i_1;
}

零钱兑换

如何列出正确的状态转移方程？

• base case amount = 0 返回0
• 确定状态 amount
• 确定选择
• 明确dp函数

定义dp函数，dp(n)表示输入一个目标金额 n，返回凑出目标金额 n 所需的最少硬币数量