0%

dp构造思路:一些经典题目解法

最长递增子序列

dp 的难点在于寻找正确的状态转移方程,这里以 最长递归子序列问题 来讲讲 dp 的通用技巧:数学归纳思想

题目 RT:

image-20200529181044741

这里子序列可以是不连续的序列。下面通过设计 dp 来解决问题。

动态规划解法

dp 的核心思路是数学归纳法。

这里我们可以这样定义:dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

根据这个定义,我们就可以推出 base case:dp[i] 初始值为 1,因此以 nums[i] 结尾的最长递增子序列起码要包含他自己。

例如:

image-20200529181902383

根据这个定义,我们的最终结果(子序列的最大长度)应该是 dp 数组中的最大值。

1
return Math.max(...dp);

那么怎么推算 dp 数组中的每个值,就是我们这里的重点内容了,这里就可以使用数学归纳法了:

假设我们已经知道了 dp[0...4] 的所有结果,我们如何根据这些结果来推出 dp[5] 呢?

image-20200529182358120

根据之前对 dp 数组的值的定义:nums[5] 值为 3,既然是递增子序列,我们只需要找前面那些结尾比 3 小的子序列,然后把 3 接到最后,就可以形成一个新的递增子序列,而且这个新的子序列长度加一。

显然,可以形成很多种新的子序列,但这里只选择最长的那一个,把最长子序列的长度当作 dp[5] 的值即可。

1
2
3
4
5
for (let j = 0;j<i;j++) {
if(nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j + 1])
}
}

这个时候我们已经可以算出 dp[5]了,其他情况依此类推即可:

1
2
3
4
5
for (let i = 0; i < nums.length; i ++) {
for (let j = 0; j < i; j ++) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}

以 base case 作为例子,看一下完整的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const solve = (nums) => {
if (nums.length === 0) {
return 0;
}
let dp = Array(nums.length).fill(1);
for (let i = 0; i < nums.length; i++) {
for (let j = 0;j < i;j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
return Math.max(...dp);
}

那么这样这道题就搞定了,总结下dp状态转移关系:

  1. 明确 dp 数组所存数据的含义。
  2. 根据 dp 数组的含义,运用数学归纳法,假设 dp[0...i-1] 都已知,想办法求出 dp[i],一旦这一步完成,这题就 ac 了。

最大子数组

image-20200529184953233

思路分析

解这个题目需要dp技巧,但 dp 数组定义比较特殊。按照常规的 dp 思路,一般是这样定义 dp 数组:

nums[0...i] 中的 “最大子数组和” 为 dp[i]

如果这样定义,整个 nums 数组的“最大子数组和”就是dp[n-1]。那么这样要如何找到状态转移方程式呢?按照数学归纳法,假设我们知道了 dp[i-1],如何往 dp[i] 推?

如下图,按照我们对 dp 数组的定义,dp[i] = 5,也就是等于 nums[0...i] 中的最大子数组和:

image-20200529194733844

在上图这种情况中,利用数学归纳法是不能从 dp[i] 推出 dp[i+1] 的。

因为子数组一定是连续的,按照我们当前 dp 数组定义,并不能保证 nums[0...i] 中的最大子数组于 nums[i+1] 是相邻的,也就是没有办法从 dp[i] 中推出 dp[i+1] 的。

所以我们需要重新定义 dp 数组的含义:

nums[i] 为结尾的“最大子数组和”为dp[i]

这种定义之下,想得到整个 nums 数组的“最大子数组和”,不能直接返回 dp[n-1]而是返回dp数组中的最大值。

根据数学归纳法,如果我们已经推出了 dp[i-1],那么该如何推出 dp[i] 呢?

可以做到,dp[i]有两种选择,和前面相邻的子数组连接,形成一个更大的子数组;要么不与前面的子数组连接,自成一派,自己作为一个子数组。

既然要选择子数组最大的和,当然要选择最大的子数组了:

1
dp[i] = Math.max(nums[i], dp[i-1] + nums[i])

所以正确的解法就是:

1
2
3
4
5
6
7
8
const solve = (arr) => {
let len = arr.length;
dp[0] = nums[0]
for (let i = 1;i<len;i++) {
dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
}
return Math.max(...dp);
}

0-1背包问题

这里介绍一下一些常见的背包问题,以最常见的0-1背包问题作为例子:

给你一个装载重量为 W 的背包和 N个物品,每个物品有质量和属性两个属性。其中第 i 个物品的重量为 wt[i],价值为 val[i],现在用这个背包装物品,最多能装的价值是多少?

image-20200530145726517

举个简单例子,输入例如:

1
2
3
N = 3, W = 4;
wt = [2,1,3]
val = [4,2,3]

算法结果返回了6,选择前面两件物品装进背包,总质量3小于 W,可以获得的最大价值为6。

题目就是这么简单,一个典型的 dp 问题。这个问题中的物品不可以被分割,要么装进背包,要么不装,不能说切成两块装一半。这就是0-1背包名词的来历。

dp 套路

第一步首先要明确两点,状态和选择

先说状态,如何才能描述一个问题局面?只要给几个物品和一个背包的容量限制,就形成了一个背包问题。所以状态有两个,就是背包的容量可选择的物品

再说选择,对于每件物品,能选择的就是装进背包或者不装进背包

明白了状态和选择,动态规划问题就基本上解决了,只需要往这个框架里面套就完事了:

1
2
3
4
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 择优(选择1,选择2...)

第二步,要明确 dp 数组的定义。

首先看到刚才找到的“状态”有两个,也就是我们说的需要一个二维 dp 数组。

dp[i][w] 的定义如下:对于前 i 个物品,当前背包的容量为w,这种情况下可以装的最大价值是 dp[i][w]

例如:如果dp[3][5] = 6,其含义为:对于给定的一系列物品中,若只对前3个物品进行选择,当背包容量为5时,最多可以装下的价值为6。

为什么这样定义?便于状态转移,或者说这就是套路。

根据这个定义,我们想知道的答案就是 dp[N][W]base case就是 dp[0][...] = dp[...][0] = 0,因为没有物品或者背包空闲的时候,能装的最大价值就是 0。

细化上面的框架:

1
2
3
4
5
6
7
8
int dp[N+1][W+1]
dp[0][...] = 0
dp[...][0] = 0

for i in [1...N]:
for w in [1...W]:
dp[i][w] = max(装i物品,不装i物品 )
return dp[N][W]

第三步,根据“选择”来思考状态转移的逻辑:

简单而言,上面伪代码中“装i物品”和“不装i物品”怎么用代码体现出来呢?

这就要结合 dp 数组的定义和我们的算法逻辑来分析了:

dp[i][w]表示:对于前 i 个物品,当前背包容量为 w时,这种情况下可以装下的最大的价值是 dp[i][w]

如果没有把第 i 个物品装入背包,那么显然,最大价值 dp[i][w] 应该等于 dp[i-1][w] ,继承之前的结果。

如果把这第 i 个物品装入了背包,那么 dp[i][w]应该等于 dp[i-1][w-wt[i-1]] + val[i-1]

首先,由于 i 是从1开始的,所以 valwt 的索引是 i-1 时表示第 i 个物品的价值和重量。

dp[i-1][w-wt[i-1]]也很好理解:如果你装了第 i 个物品,就要寻求剩余质量 w-wt[i-1] 限制下的最大价值,加上第 i 个物品的价值 val[i-1]

综上两种选择,我们已经分析完毕了,也就是写出了状态转移方程式,可以进一步细化代码:

1
2
3
4
for i in [1...N]:
for w in [1...W]:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i-1]] + val[i-1])
return dp[N][W]

最后一步把伪代码翻译成代码,处理一些边界情况。

且处理一下w-wt[i-1]会使得索引小于 0 的情况。

代码如下图所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const solve = (W, N, wt, val) => {
let dp = []
for (let i = 0; i <= N; i++) {
dp[i] = []
for (let j = 0; j <= W; j++) {
dp[i][j] = 0;
}
}
for (let i = 1;i<=N;i++) {
for (let j = 1;j<=W;j++) {
// 这种情况只能不放入背包
if(j-wt[i-1] < 0) {
dp[i][w] = dp[i-1][w]
} else {
// 装入或者不装入,择优选择
dp[i][w] = max(dp[i-1][j-wt[i-1]] + val[i-1], dp[i-1][j]);
}
}
}
return dp[N][W];
}

leetcode 0-1 背包的问题可以选择 4164741049 来练习一波。

lc416 分割等和子集

image-20200530172114845

这个题目和传统的 0-1 背包并不是很像,即:

  • 0-1背包问题选取物品的容积总量不能超过规定的容量
  • 本题选取的数字之和需要恰好等于规定和的一半

因此这题的 base 应该这样去设置:

1
2
dp[0][nums[0]] = true;
dp[i][0] = true

先找一下状态,状态首先有元素的数目,以及这些对应元素里面是否有值能够去填补相对应的和。

于是可以这样来设置一个状态:

dp[i][j] 表示 0~i 个元素里面是否存在和为 j 的子集:

选择是这样的:

1
2
3
for 选择 in 初始数组
for 元素 in 和的一半
dp[选择区间元素][元素] = dp[选择区间元素-1][元素] || dp[选择区间元素-1][元素 - 选择]

那么这次的核心dp代码就是这样的了:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 初始化一下边界
dp[i][0] = true
dp[0][nums[0]] = true;
for (let i = 1;i<nums.length;i++) {
for (let j = 0;j<=sum / 2;j++) {
if (j >= nums[i]) {
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
} else {
dp[i][j] = dp[i-1][j]
}
}
}
return dp[nums.length - 1][sum / 2]

474. 一和零

image-20200601125804588

这题和 0-1 背包有点不一样的区别在于 0-1 背包板子里面是只有一个背包容量的,但是这种情况下是可以需要2个背包的,一个用来存取0的数目,一个用来存1的数目, 因此这里我们开需要开两个背包容量来去计算:

dp[k][i][j] 该状态的意思指的是在子区间 0 ~ k 中使用 i 个 0 和 j 个 1 能得到的最多字符串的数目。

状态转移方程式为:

dp[k][i][j] = Math.max(dp[k-1][i][j], dp[k-1][i-当前字符串0的数目][j-当前字符串1的数目])

因此核心代码可以这样来推:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const solve = (strs, m, n) => {
// 初始化的全初始化为0
let dp[strs.length][m][n] = {0}
let index = 1
for (let str of strs) {
for (let i = 0;i<=m;i++) {
for (let j = 0;j<=n;j++) {
dp[index][i][j] = dp[index-1][i][j];
if (i >= countZero(str) && j >= countOne(str)) {
// 这里也是和0,1背包的两种选择,放或者不放当前的字符串
dp[index][i][j] = Math.max(dp[index-1][i][j], dp[index-1][i-countZero(str)][j-countOne(str)])
}
}
}
index++
}
return dp[strs.length][m][n];
}