1 - 动态规划入门

算法题冲冲冲!

基本概念

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

  • 只有 列出正确的“状态转移方程”,才能正确地穷举。
  • 需要判断算法问题是否 具备“最优子结构”,是否能通过子问题的最值得到原问题的最值。
  • 动态规划还 存在”重叠子问题“,直接暴力递归效率很低。所以需要用”备忘录“或”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 + 19 + 26 + 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的算法笔记》