对于动态规划的思考

宋正兵 on 2021-04-20

这篇博客打算记录我在遇到动态规划题目时的一些思考。

1 最大子序和

最大子序和

题目大意:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

因为之前做过这道题,但是脑子里还留有的印象只有定义一个变量 sum 一直累加,当 sum < 0 的时候就令 sum = 0,同时记录最大值,但是对该问题没有一个清晰的思考,回寝室路上同 JCWang 讨论这道理颇受启发,故记录下来思考过程。

思考过程

首先看题目我们能有一个直觉是:利用动态规划一定能做!那么如何去定义 状态变量 呢?

我们首先需要知道,**【动态规划】的核心是让我们可以从最简单的情况开始考虑,通过逐步递推,每一步都能记住当前问题的答案,然后得到最终问题的答案。**这是一种【自底向上】思考问题的思路。

它不同于【记忆化递归】,记忆化递归是直接面对问题的求解,遇到一个问题后,通过缓存的方式将该问题的答案记录下来,下次遇到相同问题的时候从缓存中直接拿出答案。

回到这道题目本身,思考一个问题,我们的状态变量应该是设置为从第 i 个元素开始的最大和还是以第 i 个元素结尾的最大和呢?

如果选择“从第 i 个元素开始的最大子序和”,在最坏的情况下,遍历每一个开始元素都会一直执行到数组末尾。时间复杂度高不说,对于前一个状态 dp[i - 1] 也用不上来,这就谈不上是动态规划。

选择“以第 i 个元素结尾的最大子序和”,我们可以利用前一个状态 dp[i - 1] 来推断当前求得的和是否是最大和,来更新 dp[i],即 dp[i] = max(dp[i - 1] + nums[i], nums[i])

递推式的获得取决于你对状态变量的定义,通过状态变量的定义观察当前状态和上一个状态的关系来确定你的递推式。

好了,现在我们确定递推式为 dp[i] = max(dp[i-1] + nums[i], nums[i]),根据该递推式遍历完整个数组后,状态变量数组中最大的即我们要的答案。

代码

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int max = nums[0];
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
// 遍历的同时更新状态变量的最大值
if (dp[i] > max) {
max = dp[i];
}
}
return max;
}
}

优化空间复杂度

分析上述过程,我们发现当前状态 dp[i] 之和上一个状态 dp[i - 1] 有关,于是我们可以只用一个变量 sum 来维护对于当前的 dp[i] 来讲,dp[i - 1] 应该是多少,从而让空间复杂度降低到 $O(1)$,类似于【滚动数组】的思想。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int sum = 0, max = nums[0];
for (int i = 0; i < n; i++) {
sum = Math.max(sum + nums[i], nums[i]);
max = Math.max(max, sum);
}
return max;
}
}

2 扩展阅读——三种遍历子串或者子序列的方式

示例: [a, b , c, d , e]

通常我们遍历子串或者子序列有三种遍历方式

  • 以某个节点为开头的所有子序列:如 [a],[a, b],[ a, b, c] … 再从以 b 为开头的子序列开始遍历 [b] [b, c]。
  • 根据子序列的长度为标杆,如先遍历出子序列长度为 1 的子序列,在遍历出长度为 2 的等等。
  • 以子序列的结束节点为基准,先遍历出以某个节点为结束的所有子序列,因为每个节点都可能会是子序列的结束节点,因此要遍历下整个序列,如:以 b 为结束点的所有子序列: [a , b] [b] 以 c 为结束点的所有子序列: [a, b, c] [b, c] [ c ]。

第一种遍历方式通常用于暴力解法, 第二种遍历方式 leetcode (5. 最长回文子串 ) 中的解法就用到了。

第三种遍历方式因为可以产生递推关系,采用动态规划时,经常通过此种遍历方式,如背包问题,最大公共子串,这里的动态规划解法也是以先遍历出以某个节点为结束节点的所有子序列的思路

作者:lao-hu-8
链接:https://leetcode-cn.com/problems/maximum-subarray/solution/xiang-xi-jie-du-dong-tai-gui-hua-de-shi-xian-yi-li/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

3 解码方法

解码方法

题目大意:一条包含字母 A-Z 的消息通过以下映射进行了 编码

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数

思路1 递归

把解码字符串的过程看作是一棵树,对于每个节点我们都有 单独解码 或者 联合解码 两种选择去生成该节点的子节点。

  • 退出条件:
    • 搜索完最后一个字符:表示找到了一种解码方法,返回 1
    • 当前子串的第一个字符为 0:当前解码方法走不下去了,返回 0;
  • 单独解码:如果第 i 位字符大于 0,那么一定能够单独解码,下一次解码从第 i+1 位开始;
  • 联合解码:如果第 i 位字符和第 i-1 位字符组成的数字在 [10,26] 之内就可以进行联合解码;
  • 如果同时单独解码和联合解码,那么 解码方法的总数 = 单独解码 + 联合解码

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int numDecodings(String s) {
int n = s.length();
if (n == 0) {
return 1;
}
char ch = s.charAt(0);
if (ch == '0') {
return 0;
}
// 一棵树的形式,一层一层的往下解码,每个节点都有单独自己解码和联合下一个字符解码两种选择
// 当前字字符不为'0',必定能自己单独解码
int count = numDecodings(s.substring(1));
// 判断是否能和下一个字符联合解码
if (n > 1) {
if (ch == '1' || (ch == '2' && s.charAt(1) <= '6')) {
count += numDecodings(s.substring(2));
}
}
return count;
}
}

很显然,它会超时。

思路2 优化递归,记忆化搜索

分析递归的代码,发现我们重复计算了多次 numDecodings(s[index,n])s[index,n] 是字符串 s 的子串,ns 的长度。那么我们可以开辟一块内存空间来存储计算的结果,下次遇到相同的计算直接返回。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
// 记忆化搜索
int[] buffer;
public int numDecodings(String s) {
char[] arr = s.toCharArray();
buffer = new int[arr.length];
return decodings(arr, 0);
}
public int decodings(char[] arr, int index) {
if (index == arr.length) {
return 1;
}
// 搜索缓存
if (buffer[index] != 0) {
return buffer[index];
}
if (arr[index] == '0') {
return 0;
}
// 一棵树的形式,一层一层的往下解码,每个节点都有单独自己解码和联合下一个字符解码两种选择
// 当前字字符不为'0',必定能自己单独解码
int count = decodings(arr, index + 1);
// 判断是否能和下一个字符联合解码
if (arr.length - index > 1) {
if (arr[index] == '1' || (arr[index] == '2' && arr[index + 1] <= '6')) {
count += decodings(arr, index + 2);
}
}
// 存入缓存
buffer[index] = count;
return count;
}
}

这下不超时了,但是还能不能继续优化呢?

思路3 动态规划

有些人啊,他就是吃饱了撑的。

递归的方法时间复杂度确实高,那么就可以去考虑递推的解法。

前面有过分析,对于第 i 位字符,有两种选择,一种是自己单独解码,另外一种是联合第 i+1 位字符进行解码。但是我们是用递推诶!你联合第 i+1 位字符,我们的递推就是去推第 i+1 位的状态,所以我们把它换成是联合第 i - 1 位字符进行解码。(第 i+1 位也不是不行,只不过一个是从左往右递推,一个是从右往左递推罢了)

那么我们定义状态变量 dp[i] 表示前 i 位字符的解码方法的总数。对于第 i 位字符,有三种情况存在:

  • 只能自己单独解码
  • 只能联合前一位字符解码
  • 既能自己单独解码,又能联合前一位字符解码

于是可以得到状态转移方程:

  • dp[i] = dp[i - 1],只能自己单独解码;
  • dp[i] = dp[i - 2],只能联合前一位字符解码;
  • dp[i] = dp[i - 1] + dp[i - 2],既能自己单独解码,又能联合前一位字符解码

代码:【细节】由于题目存在前导零,而前导零不能被解码,可以进行特判,也可以往字符串头部追加空格作为哨兵,追加空格既可以避免讨论前导零,也能使下标从 1 开始,简化 dp[i-2] 等负数下标的判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int numDecodings(String s) {
s = " " + s;
int n = s.length();
char[] arr = s.toCharArray();
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
// 独自编码[1,9]
if (arr[i] > '0') {
dp[i] += dp[i - 1];
}
// 联合编码[10,26] || // 既能独自又能联合
if (arr[i - 1] == '1' || (arr[i - 1] == '2' && arr[i] <= '6')) {
dp[i] += dp[i - 2];
}
}
return dp[n - 1];
}
}

思路4 空间优化

来了来了,随迟但到。对于 dp[i] 来讲,我们只用到了 dp[i - 1]dp[i - 2],所以我们只需要开辟一个长度为 3 的数组即可。通过取余的方式循环复用不需要的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int numDecodings(String s) {
s = " " + s;
int n = s.length();
char[] arr = s.toCharArray();
int[] dp = new int[3];
dp[0] = 1;
for (int i = 1; i < n; i++) {
dp[i % 3] = 0;
// 独自编码[1,9]
if (arr[i] > '0') {
dp[i % 3] += dp[(i - 1) % 3];
}
// 联合编码[10,26] || // 既能独自又能联合
if (arr[i - 1] == '1' || (arr[i - 1] == '2' && arr[i] <= '6')) {
dp[i % 3] += dp[(i - 2) % 3];
}
}
return dp[(n - 1) % 3];
}
}

学习的时候啥都好讲,做题的时候能够写出来 AC 才是正道。