跳到主要内容

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);
}

它的递归树如下：

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

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

消除重叠子问题​

自顶向下记忆化递归​

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

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

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];
    }
}

它的递归树如下：

可见每个子问题只计算了一次，时间复杂度便降到O(N)O(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] = ...就是 状态转移方程：

f(n)={1,n=1,2f(n−1)+f(n−2),n>2\nonumber f\left(n\right)= \begin{cases} 1,\quad n=1,2\\ f\left(n-1\right)+f\left(n-2\right),\quad n>2 \end{cases}

状态转移方程是解决动态规划问题的核心。

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

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;
}

这样空间复杂度就是O(1)O(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，返回要凑出目标金额所选择硬币的最小数量。

得到状态转移方程如下：

dp(n)={−1,n<00,n=0min{dp(n−coin)+1 ∣ coin∈coins},n>0\nonumber dp\left(n\right)= \begin{cases} -1,\quad n<0\\ 0,\quad n = 0\\ \mathrm{min}\{dp(n-coin)+1\ |\ coin\in coins\},\quad n>0 \end{cases}

综上，可以写出直接递归的代码：

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，那么子问题总数为kNk^N。然后是每个子问题所需时间，需要循环k次，复杂度为O(k)O(k)。综上，时间复杂度为O(kN+1)O(k^{N+1})​，又是指数复杂度，肯定会超时。

消除重叠子问题​

记忆化递归​

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

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];
}

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

自底向上迭代​

当然，也能自底向上迭代做，这样也能消除重叠子问题。定义 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. 爬楼梯​

dp数组含义

dp[i]：爬到 i 楼有 dp[i] 种方法。

状态转移方程

dp[i] = dp[i - 1] + dp[i - 2]，可以从dp[i - 1]上一节来到本层，也能从dp[i - 2]上两节来到本层。

初始化

dp[0] = 0, dp[1] = 1, dp[2] = 2

遍历方式

从前往后

代码

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

746. 使用最小花费爬楼梯​

dp数组含义

dp[i]：爬到 i 层时的最小花费。

状态转移方程

dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

初始化

dp[0] 和 dp[1] 均为0, 因为开头选择从0还是1开始上，不需要花费

遍历方式

从前往后

代码

int minCostClimbingStairs(vector<int>& cost) {
    vector<int> dp(cost.size() + 1, 0);
    for (int i = 2; i <= cost.size(); ++i)
    {
        dp[i] = min(dp[i - 1] + cost[i - 1],
        dp[i - 2] + cost[i - 2]);
    }
    return dp[cost.size()];
}
377. 组合总和 Ⅳ 本质是爬楼梯，相当于每次往上爬 nums[i] 步
2466. 统计构造好字符串的方案数 1694
2266. 统计打字方案数 1857
2533. 好二进制字符串的数量（会员题）

打家劫舍​

198. 打家劫舍​

dp数组定义

dp[i]：从第0家到第i家抢到的最大钱数。

状态转移方程

dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]),一共有两个操作：

  • 抢第i家：要抢第i家，需要从dp[i-2]接着抢，那么钱为dp[i - 2] + nums[i]；
  • 不抢第i家：最大钱数为dp[i - 1]，因为抢了第i - 1家就不能抢相邻的第i家了；

初始化

  • dp[0] = nums[0]：抢第0家的最大钱数为nums[0]；
  • `dp[1] = max(nums[0], nums[1])：抢第1家就得不抢第0家，在抢和不抢之间取最大；

代码

int rob(vector<int>& nums) {
    if (nums.size() == 0)
    {
        return 0;
    }
    else if (nums.size() == 1)
    {
        return nums[0];
    }

    vector<int> dp(nums.size());
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < nums.size(); ++i)
    {
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[nums.size() - 1];
}

213. 打家劫舍 II​

变成环形了，需要进行两次打家劫舍（也就是抢不抢第0家）：

  • 包含首元素，不包含尾元素
  • 包含尾元素，不包含首元素

然后取两次结果的最大值即可，代码如下：

int rob(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    if (nums.size() == 1) return nums[0];

    auto Rob = [&](int start, int end) -> int
    {
        if (start > end) return 0;
        if (start == end) return nums[start];

        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        
        for (int i = start + 2; i <= end; ++i)
        {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    };

    return max(Rob(0, nums.size() - 2), Rob(1, nums.size() - 1));
}
740. 删除并获得点数
2320. 统计放置房子的方式数 1608

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

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

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

参考资料​

  • 《labuladong的算法笔记》