动态规划框架

动态规划：Dynamic Programming

动态规划问题的一般形式就是求最值 -> 穷举

动态规划的穷举特点在于这类问题存在重叠子问题，如果暴力穷举，效率极其低下。所以一般通过备忘录或者DP table用空间来优化穷举的过程，避免不必要的计算。

动态规划三要素：重叠子问题、最优子结构、状态转移方程

重叠子问题：
最优子结构：
状态转移方程：穷举的方式

思维框架：
明确base case -> 明确[状态] -> 明确[选择] -> 定义dp数组、函数的含义

代码框架：

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

下面以例子方式详解动态规划的基本原理

斐波那契数列问题

509.斐波那契数
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

提示：

0 ≤ N ≤ 30

由题意可以推到出一下递推公式：

方法一：暴力递归

//方法一：递归
int fib(int n)
{
    // base case
    if (n == 0 || n == 1)
    {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

方法二：递归 + 备忘录(自顶向下)

//方法二：递归 + 备忘录（自顶向下）
int helper(int *rec_table, int n)
{
    if (n == 0 || n == 1)
    {
        return n;
    }
    if (rec_table[n] != 0)
    {
        return rec_table[n];
    }
    rec_table[n] = helper(rec_table, n - 1) + helper(rec_table, n - 2);
    return rec_table[n];
}
int fib(int n)
{
    if (n == 0 || n == 1)
    {
        return n;
    }
    int *rec_table = (int *)malloc((n + 1) * sizeof(int));
    memset(rec_table, 0, (n + 1) * sizeof(int));
    rec_table[0] = 0;
    rec_table[1] = 1;
    return helper(rec_table, n);
}

方法三：动态规划 + dp数组

// 方法三：动态规划，数组/滚动变量
int fib(int n)
{
    if (n == 0 || n == 1)
    {
        return n;
    }
    int *dp = (int *)malloc((n + 1) * sizeof(int));
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}