算法题冲冲冲！

基本概念

动态规划问题的一般形式就是求最值。求解动态规划的核心问题是穷举，但并不容易：

• 只有 列出正确的“状态转移方程”，才能正确地穷举。
• 需要判断算法问题是否 具备“最优子结构”，是否能通过子问题的最值得到原问题的最值。
• 动态规划还 存在”重叠子问题“，直接暴力递归效率很低。所以需要用”备忘录“或”DP table“来优化穷举过程，避免不必要的计算。

求解状态转移方程的一般思路如下：

明确最初条件 -> 明确”状态“ -> 明确”选择“ -> 定义 dp 数组/函数的含义。

然后就能进行递归求解了，分为 自顶向下递归 和 自底向上迭代 两种写法。

一般框架如下：

# 自顶向下递归
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代
# 初始化最初条件
dp[0][0][...] = base_case
# 进行状态转移
for 状态1 in 状态1所有取值:
    for 状态2 in 状态2所有取值:
        for ...:
            dp[状态1][状态2][...] = 求最值(选择1, ...)

求解斐波那契数列

509. 斐波那契数 - 力扣（LeetCode）

直接递归

暴力求解斐波那契数列的代码如下：

int fib(int n)
{
    if (n == 1 || n == 2)	return 1;
    return fib(n - 1) + fib(n - 2);
}

它的递归树如下：

从递归树可以看出，子问题的个数为；从代码可以看出，求解一个子问题的时间为。综上该算法时间复杂度为，超级慢。

这是因为 存在大量重复计算，这正是动态规划问题的第一个性质：重叠子问题。

消除重叠子问题

自顶向下记忆化递归

为了避免重复计算，可以花费一点空间去存储子问题的计算结果，可以用数组或哈希表来存储。

使用记忆化递归的代码如下：

int fib(int n)
{
    vector<int> memo(n + 1, 0);
    return helper(memo, n);
}

int helper(vector<int>& memo, int n)
{
    // 初始条件
    if (n == 0 || n == 1)	return n;
    // 记忆化递归
    if (memo[n] != 0)	return memo[n];
    else
    {
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
        return memo[n];
    }
}

它的递归树如下：

可见每个子问题只计算了一次，时间复杂度便降到​。

自底向上迭代

除了自顶向下递归，还可以从f(1)，f(2)自底向上推导，直到推到想要的答案，这也消除了重复的运算。代码如下：

int fib(int n) {
    if (n == 0) return 0;

    vector<int> dp(n + 1, 0);
    dp[0] = 0, dp[1] = 1;
    for (int i = 2; i <= n; ++i)
        dp[i] = dp[i - 1] + dp[i - 2];

    return dp[n];
}

其中，那一行dp[i] = ...就是 状态转移方程： 状态转移方程是解决动态规划问题的核心。

如果我们不需要前面的计算结果，可以不用数组存，而是用两个变量：

int fib(int n) {
    if (n <= 1) return n;

    int dp_0 = 0, dp_1 = 1;
    for (int i = 2; i <= n; ++i)
    {
        int dp_i = dp_1 + dp_0;
        // 更新下一阶段
        dp_0 = dp_1;
        dp_1 = dp_i;
    }

    return dp_1;
}

这样空间复杂度就是了。

凑零钱问题

322. 零钱兑换 - 力扣（LeetCode）

该问题 符合”最优子结构“。要符合最优子结构，子问题间必须互相独立。例如本题，求amount = 11时的最少硬币数（原问题）和求amount = 10, 9, 6时的最少硬币数（子问题）是相互独立的。求出子问题的答案后，再将其加一（10 + 1，9 + 2，6 + 5），就是原问题的答案了。

直接递归

1. 确定初始情况，当目标金额amount为0时，返回0.
2. 确定“状态”，也就是原问题和子问题中会变化的变量。应该是目标金额amount。
3. 确定“选择”，也就是导致“状态”产生变化的行为。这里是对新增硬币面额的“选择”。
4. 定义dp函数dp(n)。这里先考虑自顶向下的直接递归，输入目标金额n，返回要凑出目标金额所选择硬币的最小数量。

得到状态转移方程如下： 综上，可以写出直接递归的代码：

int coinChange(vector<int>& coins, int amount) {
    return dp(coins, amount);
}   

int dp(vector<int>& coins, int amount)
{
    // 初始状态:    
    //  amount = 0, 不需要凑钱 => ans = 0
    //  amount < 0, 无解 => ans = -1
    if (amount == 0)    return 0;
    if (amount < 0)   return -1;

    int res = numeric_limits<int>::max();
    for (int coin : coins)
    {
        // 递归求解子问题, 无解就跳过
        int subRes = dp(coins, amount - coin);
        if (subRes == -1)   continue;
        // 求解原问题答案(子问题+1个硬币)
        res = min(res, subRes + 1);
    }  

    return res == numeric_limits<int>::max() ? -1 : res;
}

递归算法的时间复杂度分析：子问题总数 x 解决每个子问题所需的时间

接下来分析一下直接递归的时间复杂度。首先是子问题总数，假设硬币金额数为k，那么子问题总数为。然后是每个子问题所需时间，需要循环k次，复杂度为。综上，时间复杂度为​，又是指数复杂度，肯定会超时。

消除重叠子问题

记忆化递归

那么就需要 通过记忆化递归消除重叠子问题 了，代码如下：

vector<int> m_memory;

int coinChange(vector<int>& coins, int amount) 
{
    m_memory.assign(amount + 1, -114514);
    return dp(coins, amount);
}

int dp(vector<int>& coins, int amount)
{
    if (amount == 0)    return 0;
    if (amount < 0)   return -1;
    if (m_memory[amount] != -114514)
        return m_memory[amount];

    int res = numeric_limits<int>::max();
    for (int coin : coins)
    {
        int subRes = dp(coins, amount - coin);
        if (subRes == -1)   continue;

        res = min(res, subRes + 1);
    }  

    m_memory[amount] = res == numeric_limits<int>::max() ? -1 : res;
    return m_memory[amount];
}

有了“备忘录”，子问题数量被锐减为，那么时间复杂度为，可以通过了。

自底向上迭代

当然，也能自底向上迭代做，这样也能消除重叠子问题。定义 d[i]：当目标金额为i时，至少需要d[i]枚硬币凑够。

代码如下：

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);

    // 初始条件
    dp[0] = 0;
    // 开始dp
    for (int i = 0; i < dp.size(); ++i)
    {
        for (auto coin : coins)
        {
            // 子问题无解
            if (i - coin < 0)   continue;
            // 子问题有解
            dp[i] = min(dp[i], dp[i - coin] + 1);
        }
    }

    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

这里将dp[]初始化为amount + 1是因为，dp[]最大值为amount，给它加个1相当于给它取了正无穷。

总结

解决动态规划问题的一般步骤如下：

1. 求解状态转移方程：
   1. 确定最初条件
   2. 确定要转移什么“状态”
   3. 确定要做什么“选择”才能导致状态转移
   4. 定义dp[]/dp()。
2. 写出直接递归的版本（熟练后可不写）
3. 写出记忆化递归（使用“备忘录”）/自底向上迭代（使用DP Table）的版本。

练习题

爬楼梯

70. 爬楼梯（题解）
746. 使用最小花费爬楼梯（题解）
377. 组合总和 Ⅳ 本质是爬楼梯，相当于每次往上爬 nums[i] 步
2466. 统计构造好字符串的方案数 1694
2266. 统计打字方案数 1857
2533. 好二进制字符串的数量（会员题）

打家劫舍

198. 打家劫舍
740. 删除并获得点数
2320. 统计放置房子的方式数 1608
213. 打家劫舍 II

最大子数组和/最大子段和

53. 最大子数组和
2606. 找到最大开销的子字符串 1422
1749. 任意子数组和的绝对值的最大值 1542
1191. K 次串联后最大子数组之和 1748
918. 环形子数组的最大和 1777
2321. 拼接数组的最大分数 1791
363. 矩形区域不超过 K 的最大数值和 用前缀和思考

思维扩展：
152. 乘积最大子数组

参考资料

• 《labuladong的算法笔记》