俊俊几年的头像
动态规划(Dynamic Programming)详解:从入门到 LeetCode Hot 100封面图

动态规划(Dynamic Programming)详解:从入门到 LeetCode Hot 100

动态规划(Dynamic Programming)详解:从入门到 LeetCode Hot 100

动态规划(Dynamic Programming,简称 DP)是算法中非常重要的一种思想,主要用于解决具有重复子问题和最优子结构的问题。

与普通的递归、暴力枚举相比,动态规划通过保存已经计算过的子问题结果,避免重复计算,从而降低时间复杂度。

动态规划的难点通常不在代码实现,而在于如何分析出:

  1. dp 数组究竟代表什么?
  2. 状态转移方程应该如何推导?
  3. 初始状态应该如何设置?
  4. 应该按照什么顺序遍历?
  5. 最终应该返回哪个状态?

本文结合 LeetCode Hot 100 中的经典题目,逐步讲解动态规划的核心思想、常见模型和解题方法。


一、动态规划的基本思想

1. 什么是动态规划?

动态规划的核心思想是:

将一个复杂问题拆分成多个规模更小的子问题,通过保存子问题的计算结果,避免重复计算,最终得到原问题的答案。

先看一个经典问题。

示例:斐波那契数列

斐波那契数列的定义:

\[ F(n)= \begin{cases} 0, & n=0\\ 1, & n=1\\ F(n-1)+F(n-2), & n\geq 2 \end{cases} \]

例如:

F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5

最直接的做法是使用递归:

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

但是这种方法存在一个问题:重复计算了大量相同的子问题。

例如计算 fib(5):

                fib(5)
               /      \
           fib(4)      fib(3)
          /     \      /     \
      fib(3)  fib(2) fib(2) fib(1)

可以看到,fib(3)、fib(2) 被重复计算。

随着 n 增大,重复计算会越来越严重,时间复杂度为 O(2^n) 量级。

使用动态规划优化

我们可以使用一个数组保存已经计算出的结果。

int fib(int n) {
    if (n <= 1) {
        return n;
    }
vector&lt;int&gt; dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i &lt;= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}

这里:

dp[i] = dp[i - 1] + dp[i - 2];

表示第 i 个斐波那契数由前两个状态推导得到。

每个状态只计算一次,因此:

  • 时间复杂度:O(n)。
  • 空间复杂度:O(n)。

还可以进一步优化空间:

int fib(int n) {
    if (n <= 1) {
        return n;
    }
int a = 0;
int b = 1;
for (int i = 2; i &lt;= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}

因为计算当前状态只需要前两个状态,所以不需要保存整个数组。

  • 时间复杂度:O(n)。
  • 空间复杂度:O(1)。

这就是动态规划的基本思想:保存已经计算过的结果,利用之前的状态推导当前状态。

2. 动态规划的两个重要特征

并不是所有递归问题都适合使用动态规划,通常需要关注两个特征。

(1)最优子结构

原问题的最优解可以由子问题的最优解推导得到。

例如,打家劫舍问题中,考虑前 i 间房屋能够获得的最大金额,可以根据前面较小规模问题的最优结果推导。

(2)重叠子问题

在递归求解过程中,相同的子问题会被反复计算。

例如斐波那契数列:

fib(5)
  ├── fib(4)
  │     └── fib(3)
  └── fib(3)

fib(3) 被计算了多次。

动态规划通过保存子问题的结果,避免重复计算。


二、动态规划的解题步骤

这是整篇文章最重要的部分。拿到一道动态规划题目,不要急着写代码,建议按照下面六个步骤进行分析。

第一步:确定 dp 数组的含义

首先明确:dp[i] 到底表示什么? 这是动态规划最关键的一步。

例如爬楼梯问题:

dp[i]

表示到达第 i 阶楼梯,一共有多少种不同的方法。

再例如打家劫舍:

dp[i]

表示考虑前 i 间房屋时,能够偷窃到的最高金额。

不同题目中,dp 数组的含义可能完全不同。

第二步:确定状态转移方程

状态转移方程表示当前状态如何由之前的状态推导得到。

例如爬楼梯:

\[ dp[i]=dp[i-1]+dp[i-2] \]

因为到达第 i 阶楼梯,最后一步只有两种情况:

  • 从第 i-1 阶爬一步。
  • 从第 i-2 阶爬两步。

所以将两种情况相加即可。

第三步:确定初始化条件

动态规划需要从已知状态开始推导。例如:

dp[0] = 1;
dp[1] = 1;

这些初始值必须符合 dp 数组的定义。初始化错误,后面的状态转移即使正确,也可能得到错误答案。

第四步:确定遍历顺序

动态规划通常需要按照一定顺序遍历。例如:

for (int i = 2; i <= n; i++)

因为 dp[i] 依赖 dp[i-1] 和 dp[i-2],所以必须先计算较小的状态。

对于二维动态规划,还需要分析两个维度的遍历顺序。

第五步:确定最终返回值

需要明确最终答案存放在哪里。例如:

return dp[n];

但并不是所有题目都返回 dp[n]。有些题目返回:

return dp[m][n];

有些题目需要遍历整个 dp 数组,找到最大值。

第六步:考虑空间优化

如果当前状态只依赖前面少量状态,可以考虑压缩 dp 数组。

例如斐波那契数列只依赖前两个状态,可以使用两个变量代替整个数组。

但是空间优化应该放在状态转移方程确定之后,不要一开始就急着优化。

动态规划解题模板
1. 确定 dp 数组的含义
2. 推导状态转移方程
3. 确定初始化条件
4. 确定遍历顺序
5. 确定最终返回值
6. 考虑空间优化

后面的题目都按照这个思路进行分析。


三、一维动态规划

一维动态规划是最基础的动态规划模型,通常使用一维数组 dp[i] 表示某个位置或某个规模下的状态。

1. LeetCode 70:爬楼梯

题目链接:70. 爬楼梯 - 力扣(LeetCode)

题目描述

假设你正在爬楼梯,需要 n 阶才能到达楼顶。每次可以爬 1 阶或者 2 阶。问有多少种不同的方法可以爬到楼顶?

例如:

n = 3
有三种方法:
1 + 1 + 1
1 + 2
2 + 1
输出:3
解题思路

这道题是动态规划最经典的入门题目。

① 确定 dp 数组的含义

定义:

dp[i]

表示到达第 i 阶楼梯的不同方法数量。

② 确定状态转移方程

到达第 i 阶楼梯,只有两种可能:

  • 从第 i-1 阶爬一步。
  • 从第 i-2 阶爬两步。

因此:

\[ dp[i]=dp[i-1]+dp[i-2] \]

③ 确定初始化条件

dp[0] = 1;
dp[1] = 1;

这里 dp[0] = 1 表示从起点出发、不进行任何操作,有一种方式到达起点。这个定义是为了让状态转移方程统一成立。

④ 确定遍历顺序

从小到大遍历:

for (int i = 2; i <= n; i++)

因为当前状态依赖前两个状态。

⑤ 确定返回值

return dp[n];
代码实现
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
    for (int i = 2; i &lt;= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
return dp[n];
}
};
空间优化

当前状态只依赖前两个状态,因此可以使用两个变量代替数组。

class Solution {
public:
    int climbStairs(int n) {
        int a = 1;
        int b = 1;
    for (int i = 2; i &lt;= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
return b;
}
};

复杂度分析:

  • 时间复杂度:O(n)。
  • 空间复杂度:O(1)。

总结:爬楼梯问题本质上是斐波那契数列模型,重点是理解当前状态如何由前面的两个状态推导得到。


2. LeetCode 198:打家劫舍

题目链接:198. 打家劫舍 - 力扣(LeetCode)

题目描述

一个专业的小偷计划偷窃沿街的房屋。每间房屋都有一定数量的现金,但是相邻房屋安装了防盗系统。如果两间相邻的房屋在同一晚上被偷窃,系统会自动报警。

给定一个数组 nums,表示每间房屋中的金额。求在不触发警报的情况下,能够偷窃到的最高金额。

例如:

nums = [1,2,3,1]
输出:4
偷窃第 1 间和第 3 间房屋:
1 + 3 = 4
解题思路

这道题的核心是:当前房屋偷还是不偷?

① 确定 dp 数组的含义

定义:

dp[i]

表示考虑前 i 间房屋时,能够偷窃到的最高金额。

注意:这里的 i 表示房屋数量,因此数组下标从 0 开始时,需要注意下标转换。为了方便理解,我们定义:

dp[0]:考虑前 0 间房屋的最大金额
dp[1]:考虑前 1 间房屋的最大金额
dp[2]:考虑前 2 间房屋的最大金额

② 确定状态转移方程

对于第 i 间房屋,有两种选择。

情况一:不偷当前房屋。那么最大金额就是前 i-1 间房屋的最大金额:

\[ dp[i]=dp[i-1] \]

情况二:偷当前房屋。由于不能偷相邻房屋,所以只能加上前 i-2 间房屋的最大金额:

\[ dp[i]=dp[i-2]+nums[i-1] \]

两种情况取最大值:

\[ dp[i]=\max(dp[i-1],dp[i-2]+nums[i-1]) \]

③ 初始化条件

dp[0] = 0;
dp[1] = nums[0];

④ 遍历顺序

从前往后遍历:

for (int i = 2; i <= n; i++)

⑤ 返回值

return dp[n];
代码实现
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 0;
        dp[1] = nums[0];
    for (int i = 2; i &lt;= n; i++) {
        dp[i] = max(
            dp[i - 1],
            dp[i - 2] + nums[i - 1]
        );
    }
return dp[n];
}
};

注意:LeetCode 本题保证 nums 至少有一个元素,因此上述初始化成立。如果写成通用函数,需要额外处理空数组。

空间优化

当前状态只依赖前两个状态,可以使用两个变量:

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0;
        int prev1 = 0;
    for (int num : nums) {
        int cur = max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = cur;
    }
return prev1;
}
};

复杂度分析:

  • 时间复杂度:O(n)。
  • 空间复杂度:O(1)。

总结:打家劫舍的关键是将每间房屋的选择分成两种情况:

  • 偷当前房屋。
  • 不偷当前房屋。

然后根据两种情况的结果取最大值。这种根据不同选择推导状态的方式,在动态规划中非常常见。


四、背包问题

背包问题是动态规划中非常重要的一类模型。它的核心思想是:给定一定容量的背包,以及若干物品,每个物品具有一定的重量和价值,需要根据限制条件选择物品,使最终收益最大或者满足某种目标。

常见类型:

  1. 0-1 背包:每件物品只能选择一次。
  2. 完全背包:每件物品可以选择无限次。

其中最需要掌握的是两者的遍历顺序区别。

1. 0-1 背包和完全背包的区别

假设:

背包容量:10
物品:
重量:2,价值:3
重量:3,价值:4
重量:5,价值:6

0-1 背包中,每件物品最多只能选择一次。完全背包中,每件物品可以重复选择。

在一维 dp 数组中,两者最重要的区别是容量遍历方向:

类型容量遍历方向原因
0-1 背包从大到小防止当前物品被重复使用
完全背包从小到大允许当前物品重复使用

例如:

// 0-1 背包
for (int j = W; j >= weight[i]; j--) {
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
// 完全背包
for (int j = weight[i]; j <= W; j++) {
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}

为什么方向不同?因为一维 dp 数组会覆盖之前的状态。

  • 从大到小:计算当前容量时,dp[j-weight[i]] 仍然是上一轮物品处理后的状态,因此当前物品不会被重复使用。
  • 从小到大:计算当前容量时,dp[j-weight[i]] 可能已经包含了当前物品,因此允许重复使用。

这是背包问题非常重要的知识点。

2. LeetCode 322:零钱兑换

题目链接:322. 零钱兑换 - 力扣(LeetCode)

题目描述

给定不同面额的硬币 coins,以及一个总金额 amount。每种硬币可以使用无限次。求凑成总金额所需的最少硬币数量。如果无法凑成该金额,返回 -1。

例如:

coins = [1,2,5]
amount = 11
输出:3
因为:
5 + 5 + 1 = 11
解题思路

这道题属于完全背包问题,因为每种硬币可以重复使用。

① 确定 dp 数组的含义

定义:

dp[i]

表示凑成金额 i 所需要的最少硬币数量。

② 确定状态转移方程

假设当前选择一枚面额为 coin 的硬币,那么之前需要凑成的金额为:

i - coin

如果之前凑成该金额需要 dp[i-coin] 枚硬币,那么当前总共需要 dp[i-coin] + 1 枚硬币。

因为可以选择不同面额,所以需要取最小值:

\[ dp[i]=\min(dp[i],dp[i-coin]+1) \]

③ 初始化条件

dp[0] = 0;

凑成金额 0 不需要任何硬币。其他金额初始化为一个较大的数:

vector<int> dp(amount + 1, amount + 1);

因为最多使用 amount 枚面额为 1 的硬币,如果无法凑成,最终就不会得到有效结果。

④ 遍历顺序

这里使用完全背包的遍历方式:

for (int coin : coins) {
    for (int i = coin; i <= amount; i++) {
        ...
    }
}

金额从小到大遍历,允许当前硬币被重复使用。

⑤ 返回值

如果:

dp[amount] == amount + 1

说明无法凑成目标金额,返回 -1。否则返回 dp[amount]。

代码实现
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
    for (int coin : coins) {
        for (int i = coin; i &lt;= amount; i++) {
            dp[i] = min(
                dp[i],
                dp[i - coin] + 1
            );
        }
    }
return dp[amount] == amount + 1
    ? -1 : dp[amount];
}
};
关键点分析

① 为什么初始化为 amount + 1?

因为最坏情况下,如果存在面额为 1 的硬币,凑成金额 amount 最多需要 amount 枚硬币。因此 amount + 1 可以作为一个不可能达到的初始值。

② 为什么金额要从小到大遍历?

因为每种硬币可以重复使用。例如:

coins = [2]
amount = 4

当遍历到金额 2 时:

dp[2] = dp[0] + 1 = 1;

继续遍历金额 4:

dp[4] = dp[2] + 1 = 2;

这里 dp[2] 已经使用过当前面额的硬币,因此可以再次使用。如果从大到小遍历,就会变成每种硬币只能使用一次的 0-1 背包思路。

③ 为什么外层遍历硬币,内层遍历金额?

这种顺序属于组合型完全背包写法,每种硬币按照固定顺序处理,避免将不同硬币的选择顺序重复计算。

本题只求最少硬币数量,改变遍历顺序也能得到正确的最少数量,但要注意:如果题目改为统计组合数或排列数,遍历顺序就会影响答案。

复杂度分析
  • 时间复杂度:O(n × amount),n 为硬币种类数量。
  • 空间复杂度:O(amount)。

五、字符串动态规划

字符串动态规划通常使用二维 dp 数组,状态一般与两个字符串的前缀、子串或者下标有关。

1. LeetCode 139:单词拆分

题目链接:139. 单词拆分 - 力扣(LeetCode)

题目描述

给定一个字符串 s 和一个字符串列表 wordDict。判断是否可以使用字典中的单词拼接出字符串 s。字典中的单词可以重复使用。

例如:

s = "leetcode"
wordDict = ["leet", "code"]
输出:true
因为:
"leet" + "code" = "leetcode"
解题思路

这道题可以使用一维动态规划。

① 确定 dp 数组的含义

定义:

dp[i]

表示字符串 s 的前 i 个字符能否被字典中的单词拼接出来。

注意:这里的 i 表示字符数量,不是最后一个字符的下标。因此:

dp[0]

表示空字符串可以被拼接出来。

② 确定状态转移方程

如果:

dp[j] == true

并且:

s[j...i-1]

是字典中的一个单词,那么:

dp[i] = true

也就是说:

\[ dp[i]=dp[j]\ \&\&\ s[j,i)\in wordDict \]

只要存在一个满足条件的 j,就可以将 dp[i] 设置为 true。

③ 初始化条件

dp[0] = true;

空字符串可以看作已经成功完成拼接。

④ 遍历顺序

从前往后遍历字符串的前缀长度。对于每个 i,枚举之前可能的切分位置 j。

⑤ 返回值

return dp[n];
代码实现
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        unordered_set<string> dict(
            wordDict.begin(), wordDict.end()
        );
        vector<bool> dp(n + 1, false);
        dp[0] = true;
    for (int i = 1; i &lt;= n; i++) {
        for (int j = 0; j &lt; i; j++) {
            if (dp[j] &amp;&amp; dict.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
return dp[n];
}
};
关键点分析

① 为什么 dp 数组长度是 n + 1?

因为这里的 dp 下标表示前缀长度。例如:

s = "leetcode"

那么:

dp[0]:空字符串
dp[1]:"l"
dp[2]:"le"
...
dp[8]:"leetcode"

所以需要 n+1 个位置。

② 为什么 dp[0] 必须初始化为 true?

例如:

s = "leet"

当我们判断前四个字符是否能够被拼接时,j = 0。如果:

dp[0] == true

并且 "leet" 在字典中,就能得到:

dp[4] = true;

如果 dp[0] 初始化为 false,那么就无法从第一个字符开始完成匹配。

复杂度分析

设字符串长度为 n,字典中单词数量为 m。

  • 时间复杂度:通常可按 O(n²) 次状态判断理解;考虑 substr() 和哈希计算的实际开销,最坏情况下可能达到 O(n³) 量级。
  • 空间复杂度:O(n + 字典存储空间)。

六、子序列动态规划

子序列问题是动态规划中非常重要的一类题目,通常需要考虑:

  • 当前元素是否加入子序列。
  • 当前元素和之前元素之间的关系。
  • 两个字符串之间的匹配关系。

1. LeetCode 300:最长递增子序列

题目链接:300. 最长递增子序列 - 力扣(LeetCode)

题目描述

给定一个整数数组 nums,找到其中最长严格递增子序列的长度。

例如:

nums = [10,9,2,5,3,7,101,18]
输出:4
最长递增子序列:
[2,3,7,101]

注意:子序列不要求连续,但元素之间的相对顺序不能改变。

解题思路

① 确定 dp 数组的含义

定义:

dp[i]

表示以 nums[i] 结尾的最长严格递增子序列的长度。

注意,这里必须强调:dp[i] 表示以第 i 个元素结尾,而不是前 i 个元素中的最长递增子序列长度。

② 确定状态转移方程

对于当前元素 nums[i],我们需要遍历它前面的所有元素。如果:

nums[j] < nums[i]

说明可以将当前元素接在以 nums[j] 结尾的递增子序列后面。那么:

\[ dp[i]=\max(dp[i],dp[j]+1) \]

其中:

\[ 0\leq j<i \]

③ 初始化条件

每个元素自身都可以构成一个长度为 1 的递增子序列:

vector<int> dp(n, 1);

④ 遍历顺序

外层从左向右遍历 i,内层遍历所有满足 j < i 的位置。

⑤ 返回值

由于 dp[i] 表示以 i 结尾的最长递增子序列,因此最终答案不一定是 dp[n-1]。需要取整个 dp 数组的最大值:

\[ ans=\max(dp[0],dp[1],...,dp[n-1]) \]

代码实现
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        int ans = 1;
    for (int i = 0; i &lt; n; i++) {
        for (int j = 0; j &lt; i; j++) {
            if (nums[j] &lt; nums[i]) {
                dp[i] = max(
                    dp[i], dp[j] + 1
                );
            }
        }
        ans = max(ans, dp[i]);
    }
return ans;
}
};
关键点分析

① 为什么判断条件是 nums[j] < nums[i]?

因为题目要求严格递增。如果使用:

nums[j] <= nums[i]

就允许相同元素出现在递增子序列中,不符合题意。

② 为什么返回最大值,而不是 dp[n-1]?

因为最长递增子序列不一定以数组最后一个元素结尾。例如:

nums = [1,3,2]

对应:

dp = [1,2,2]

最终答案是 2。虽然最后一个元素也能构成长度为 2 的子序列,但一般情况下,不能假设答案一定以最后一个元素结尾。

复杂度分析
  • 时间复杂度:O(n²)。
  • 空间复杂度:O(n)。

补充:这道题还可以使用贪心 + 二分查找优化到 O(nlogn),但那属于另一种解法,后面可以单独学习。


2. LeetCode 1143:最长公共子序列

题目链接:1143. 最长公共子序列 - 力扣(LeetCode)

题目描述

给定两个字符串 text1 和 text2,返回它们最长公共子序列的长度。

例如:

text1 = "abcde"
text2 = "ace"
输出:3
最长公共子序列:
"ace"

注意:子序列不要求连续。

解题思路

这道题是二维动态规划的经典模型。因为需要同时考虑两个字符串,所以使用二维 dp 数组。

① 确定 dp 数组的含义

定义:

dp[i][j]

表示字符串 text1 的前 i 个字符和字符串 text2 的前 j 个字符之间的最长公共子序列长度。

注意这里的 i、j 表示前缀长度。因此:

dp[0][j] = 0;
dp[i][0] = 0;

② 确定状态转移方程

分为两种情况。

情况一:当前两个字符相等。

text1[i - 1] == text2[j - 1]

说明当前字符可以加入公共子序列。因此:

\[ dp[i][j]=dp[i-1][j-1]+1 \]

情况二:当前两个字符不相等。那么至少需要放弃其中一个字符串的当前字符,分别考虑:

  • 不考虑 text1 的当前字符。
  • 不考虑 text2 的当前字符。

取两种情况的最大值:

\[ dp[i][j]=\max(dp[i-1][j],dp[i][j-1]) \]

③ 初始化条件

vector<vector<int>> dp(
    m + 1,
    vector<int>(n + 1, 0)
);

因为任意一个字符串和空字符串的最长公共子序列长度都是 0。

④ 遍历顺序

从左上角向右下角遍历。因为当前状态依赖:

dp[i-1][j-1]
dp[i-1][j]
dp[i][j-1]

这些状态都需要提前计算。

⑤ 返回值

return dp[m][n];
代码实现
class Solution {
public:
    int longestCommonSubsequence(
        string text1,
        string text2
    ) {
        int m = text1.size();
        int n = text2.size();
    vector&lt;vector&lt;int&gt;&gt; dp(
        m + 1,
        vector&lt;int&gt;(n + 1, 0)
    );
for (int i = 1; i &amp;lt;= m; i++) {
    for (int j = 1; j &amp;lt;= n; j++) {
        if (text1[i - 1] == text2[j - 1]) {
            dp[i][j] =
                dp[i - 1][j - 1] + 1;
        }
        else {
            dp[i][j] = max(
                dp[i - 1][j],
                dp[i][j - 1]
            );
        }
    }
}
return dp[m][n];
}
};
关键点分析

① 为什么字符串下标使用 i-1 和 j-1?

因为 dp 数组下标表示前缀长度,而 C++ 字符串下标从 0 开始。例如:

text1 = "abcde"

当:

i = 3;

表示考虑前 3 个字符,即 "abc"。最后一个字符的下标就是:

i - 1

也就是 text1[2]。

② 为什么字符不相等时取最大值?

因为两个字符串的当前字符不同,它们不可能同时作为当前公共子序列的最后一个字符。因此需要尝试去掉其中一个字符,看看哪种情况能得到更长的公共子序列。

复杂度分析
  • 时间复杂度:O(m × n)。
  • 空间复杂度:O(m × n)。

七、区间与二维动态规划

二维动态规划不一定都是字符串问题。有些题目需要在二维状态空间中进行计算,还有些题目需要考虑一个区间内的最优结果。这里再看两道 Hot 100 经典题目。

1. LeetCode 64:最小路径和

题目链接:64. 最小路径和 - 力扣(LeetCode)

题目描述

给定一个包含非负整数的 m × n 网格。从左上角出发,每次只能向右或者向下移动。求到达右下角的最小路径和。

例如:

grid = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出:7
路径:
1 -> 3 -> 1 -> 1 -> 1
解题思路

① 确定 dp 数组的含义

定义:

dp[i][j]

表示从左上角到达位置 (i,j) 的最小路径和。

② 确定状态转移方程

到达当前位置,只能从上方或者左方过来。因此:

\[ dp[i][j]=\min(dp[i-1][j],dp[i][j-1])+grid[i][j] \]

③ 初始化条件

起点:

dp[0][0] = grid[0][0];

第一行只能从左边过来:

dp[0][j] = dp[0][j-1] + grid[0][j];

第一列只能从上方过来:

dp[i][0] = dp[i-1][0] + grid[i][0];

④ 遍历顺序

从左上角向右下角遍历。

⑤ 返回值

return dp[m-1][n-1];
代码实现
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
    vector&lt;vector&lt;int&gt;&gt; dp(
        m,
        vector&lt;int&gt;(n, 0)
    );
dp[0][0] = grid[0][0];
// 初始化第一行
for (int j = 1; j &amp;lt; n; j++) {
dp[0][j] =
dp[0][j - 1] + grid[0][j];
}
// 初始化第一列
for (int i = 1; i &amp;lt; m; i++) {
dp[i][0] =
dp[i - 1][0] + grid[i][0];
}
// 计算其他位置
for (int i = 1; i &amp;lt; m; i++) {
for (int j = 1; j &amp;lt; n; j++) {
dp[i][j] = min(
dp[i - 1][j],
dp[i][j - 1]
) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
};
复杂度分析
  • 时间复杂度:O(m × n)。
  • 空间复杂度:O(m × n)。

2. LeetCode 72:编辑距离

题目链接:72. 编辑距离 - 力扣(LeetCode)

题目描述

给定两个单词 word1 和 word2。可以对 word1 进行以下三种操作:

  1. 插入一个字符。
  2. 删除一个字符。
  3. 替换一个字符。

求将 word1 转换成 word2 所需要的最少操作次数。

例如:

word1 = "horse"
word2 = "ros"
输出:3
解题思路

这道题是二维动态规划中比较经典的一道困难题。

① 确定 dp 数组的含义

定义:

dp[i][j]

表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需要的最少操作次数。

② 确定状态转移方程

分为两种情况。

情况一:当前字符相等。

word1[i - 1] == word2[j - 1]

说明当前字符不需要进行操作。因此:

\[ dp[i][j]=dp[i-1][j-1] \]

情况二:当前字符不相等。需要考虑三种操作。

删除:删除 word1 当前的最后一个字符。

\[ dp[i][j]=dp[i-1][j]+1 \]

插入:在 word1 末尾插入一个字符,使其与 word2 当前字符匹配。

\[ dp[i][j]=dp[i][j-1]+1 \]

替换:将 word1 当前字符替换成 word2 当前字符。

\[ dp[i][j]=dp[i-1][j-1]+1 \]

最终取三种操作的最小值:

\[ dp[i][j]=\min \begin{cases} dp[i-1][j]+1\\ dp[i][j-1]+1\\ dp[i-1][j-1]+1 \end{cases} \]

③ 初始化条件

将一个字符串转换为空字符串,需要删除它的全部字符:

dp[i][0] = i;

将空字符串转换成另一个字符串,需要插入全部字符:

dp[0][j] = j;

④ 遍历顺序

从左上角向右下角遍历。

⑤ 返回值

return dp[m][n];
代码实现
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
    vector&lt;vector&lt;int&gt;&gt; dp(
        m + 1,
        vector&lt;int&gt;(n + 1, 0)
    );
// 初始化第一列
for (int i = 0; i &amp;lt;= m; i++) {
    dp[i][0] = i;
}
// 初始化第一行
for (int j = 0; j &amp;lt;= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i &amp;lt;= m; i++) {
for (int j = 1; j &amp;lt;= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
else {
dp[i][j] = min({
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + 1
});
}
}
}
return dp[m][n];
}
};
关键点分析

① 为什么有三种状态转移?

因为题目允许三种编辑操作:

  • 删除。
  • 插入。
  • 替换。

每一种操作都对应一种之前的状态。

② 为什么字符相同时不需要操作?

因为当前两个字符已经匹配,不需要修改它们。直接继承之前的最优结果:

dp[i][j] = dp[i - 1][j - 1];

③ 为什么初始化是 i 和 j?

例如:

word1 = "abc"
word2 = ""

需要删除 3 个字符,因此:

dp[3][0] = 3;

反过来:

word1 = ""
word2 = "abc"

需要插入 3 个字符,因此:

dp[0][3] = 3;
复杂度分析
  • 时间复杂度:O(m × n)。
  • 空间复杂度:O(m × n)。

八、动态规划中的空间优化

前面很多题目都使用了二维或者一维 dp 数组。但有些情况下,当前状态只依赖前面少量状态,没有必要保存整个数组。这时可以考虑空间优化。

1. 一维数组优化

例如爬楼梯:

dp[i] = dp[i - 1] + dp[i - 2];

只需要保存前两个状态:

int a = 1;
int b = 1;
for (int i = 2; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}

空间复杂度从 O(n) 降低到 O(1)。

2. 二维数组优化成一维数组

例如最长公共子序列:

dp[i][j]

只依赖:

dp[i-1][j-1]
dp[i-1][j]
dp[i][j-1]

实际上只需要保存上一行和当前行的数据。进一步可以使用一个一维数组完成空间压缩。

class Solution {
public:
    int longestCommonSubsequence(
        string text1,
        string text2
    ) {
        int m = text1.size();
        int n = text2.size();
    vector&lt;int&gt; dp(n + 1, 0);
for (int i = 1; i &amp;lt;= m; i++) {
    int prev = 0;
    for (int j = 1; j &amp;lt;= n; j++) {
        int temp = dp[j];
        if (text1[i - 1] == text2[j - 1]) {
            dp[j] = prev + 1;
        }
        else {
            dp[j] = max(dp[j], dp[j - 1]);
        }
        prev = temp;
    }
}
return dp[n];
}
};

这里:

  • dp[j] 在更新之前,表示上一行的 dp[i-1][j]。
  • dp[j-1] 表示当前行已经更新的 dp[i][j-1]。
  • prev 保存左上角的旧状态 dp[i-1][j-1]。

通过这三个状态,就可以完成二维动态规划的状态转移。空间复杂度从 O(m × n) 降低为 O(n)。

注意:空间优化不是简单地把二维数组改成一维数组,而是必须明确每次更新时,哪些旧状态还需要保留。


九、动态规划常见问题与面试考点

1. 动态规划和递归有什么区别?

递归是一种函数调用方式,动态规划是一种解决问题的算法思想。

递归可以直接重复计算子问题,也可以通过记忆化搜索保存结果。动态规划通常使用自底向上的方式,按照状态依赖关系逐步计算。

2. 动态规划和记忆化搜索有什么区别?

两者都可以避免重复计算。

记忆化搜索:

  • 通常使用递归。
  • 从原问题开始向下搜索。
  • 遇到已经计算过的状态,直接返回保存的结果。

动态规划(通常指递推式 DP):

  • 通常使用循环。
  • 从较小的子问题开始计算。
  • 按照状态转移顺序逐步得到最终答案。

两者解决的状态关系可以相同,只是计算顺序和实现方式不同。

3. 为什么动态规划需要初始化?

因为状态转移方程需要依赖之前的状态。如果初始状态没有正确设置,就无法正确推导后续状态。

例如:

dp[0] = 1;

在爬楼梯中表示到达起点有一种方式。而在打家劫舍中:

dp[0] = 0;

表示没有房屋时,最大收益为 0。初始化必须结合 dp 数组的具体定义,不能死记硬背。

4. 为什么有些题目需要倒序遍历?

这通常出现在一维数组优化后的背包问题中。0-1 背包中,每件物品只能使用一次。如果容量正序遍历,当前物品可能被重复使用,所以需要倒序遍历。

完全背包中,每件物品可以重复使用,因此通常正序遍历容量。

5. 为什么有些动态规划题目返回 dp 数组最大值,而不是最后一个元素?

因为 dp 数组的含义可能是:

dp[i] = 以第 i 个元素结尾的最优结果

例如最长递增子序列。最长递增子序列不一定以最后一个元素结尾,因此必须遍历整个数组取最大值。

而有些题目定义:

dp[i] = 前 i 个元素的最优结果

这种情况下,最终答案通常就是 dp[n]。关键在于理解 dp 数组的定义。

6. 动态规划一定需要二维数组吗?

不一定。

  • 一维动态规划:爬楼梯、打家劫舍、零钱兑换。
  • 二维动态规划:最长公共子序列、编辑距离、最小路径和。
  • 空间优化:使用滚动数组或者少量变量保存必要状态。

数组维度取决于状态定义,而不是题目本身有几个参数。


十、LeetCode Hot 100 动态规划刷题清单

掌握前面的题目后,可以按照下面的顺序继续练习。

题号题目核心模型难度
70爬楼梯一维 DP简单
118杨辉三角二维 DP简单
198打家劫舍状态选择中等
279完全平方数完全背包中等
322零钱兑换完全背包中等
139单词拆分字符串 DP中等
300最长递增子序列子序列 DP中等
152乘积最大子数组双状态 DP中等
62不同路径二维 DP中等
64最小路径和二维 DP中等
1143最长公共子序列二维 DP中等
72编辑距离字符串 DP困难

注:具体题目集合会随 LeetCode Hot 100 版本调整,以上以经典题目为主。


十一、总结

动态规划的核心并不是背诵某个固定模板,而是建立正确的状态定义,并通过状态转移方程解决问题。

拿到一道动态规划题目时,建议按照下面的顺序分析:

  1. 确定状态:dp[i] 或 dp[i][j] 表示什么?
  2. 推导转移:当前状态可以由哪些之前的状态得到?
  3. 确定初始化:哪些状态是已知的?
  4. 确定遍历顺序:如何保证依赖的状态已经计算?
  5. 确定答案:最终应该返回哪个状态?
  6. 空间优化:是否可以减少不必要的状态存储?

动态规划需要重点掌握以下几类模型:

模型代表题目核心思路
一维 DP爬楼梯当前状态依赖前面状态
状态选择 DP打家劫舍不同选择取最优结果
背包 DP零钱兑换根据容量和物品进行状态转移
字符串 DP单词拆分枚举前缀切分位置
子序列 DP最长递增子序列考虑之前元素的影响
双序列 DP最长公共子序列同时考虑两个字符串
二维路径 DP最小路径和从相邻位置推导当前状态
编辑距离 DP编辑距离插入、删除、替换三种操作

最后一个建议:学习动态规划时,不要只看代码。每道题都应该自己在纸上写出:

dp 数组的含义
状态转移方程
初始化条件
遍历顺序
返回值

尤其是状态转移方程,一定要能够自己推导出来。

只要能够独立分析这些内容,动态规划就不再是单纯依赖背诵代码的算法,而是一套可以迁移到不同问题上的解题方法。

转载自 CSDN-专业IT技术社区

原文链接:https://blog.csdn.net/zengjiajun2006/article/details/170246336

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数:0
关注数:0
粉丝:0
文章:0
关注标签:0
加入于:--