「数据结构与算法」-动态规划

动态规划思路

要用动态规划要具备两个性质,重叠子问题和最优子问题

  • 最优子问题:如果一个问题的最优解包含了其中子问题的最优解,那么称其有最优子结构
  • 重叠子问题:当解决一个问题时,往往依赖其更小规模的子问题的解,甚至依赖与若干个规模更小的子问题的解。

如果一个问题满足这两个条件,就可以用动态规划的方法去求解。对于动态规划问题,最难的就是列出状态转移方程。可以参考下面的方式来分解问题:

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

动态规划题目

子集和问题

问题描述

给定一个正整数集合S和一个正整数M,是否在S中存在子集使得子集之和等于M。
例如:
[1,2,6,3,17,82,23,234] -> 26
Solution [0,1,6]

[1,2,6,3,17,82,23,234] -> 40
Solution [4,6]

[1,2,6,3,17,82,23,234] -> 23
Solution [6]

解题思路

对于这个问题,难点同样在于列出状态转移方程。首先我们应该先明确状态。对于一个集合$S={a_1,a_2,…,a_n}$中的每一个元素,都存在两种状态取和不取,再考虑他们的和是否等于M,但是这样的情况就有$2^n$。所以要换个思路,令dp[i][j]代表前i个元素中是否存在子集使得子集和等于j。那么对于dp[i][j]则有两种情况:

  • 如果S[i] > j,那么i一定是不再子集中的,所以dp[i][j]=dp[i-1][j],即当前数大于子集和的目标数,那么当前数对于子集和能否等于目标数没有影响,所以当前状态(dp[i][j])应该是等于不包含S[i]时的状态(dp[i-1][j])。
  • 如果S[i] <= j,也存在两种情况:S[i]不在子集中,那么dp[i][j]=dp[i-1][j];如果S[i]在子集中,那么它的状态应该和上一个状态并且目标数等于j-S[i]时的状态相等,即dp[i][j] = dp[i-1][j-S[i]]。

所以可以列出状态转移方程:

1
2
3
4
if (S[i] > j)
dp[i][j] = dp[i-1][j]
else if (S[i] <= j)
dp[i][j] = dp[i-1][j] || dp[i-1][j-S[i]]

程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<bool> > dp(nums.size()+1, vector<bool> (target+1, false));
// base case
// i=0的时候代表是空集
// j=0的时候代表要求的和也是空集,所以都为true
for (int i = 0; i < nums.size()+1; i++)
dp[i][0] = true;
// dp
for (int i = 1; i < nums.size()+1; i++){
for (int j = 1; j < target+1; j++){
if (j < nums[i-1])
dp[i][j] = dp[i-1][j];
else if (j - nums[i-1] >= 0)
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}

如果想要找到对应的子集中的元素的序号,那么可以通过以下方法:

首先我们知道如果dp[i][j]=dp[i-1][j]=true,那么这代表S[i]不在子集中;但是如果dp[i][j]=true,[i-1][j]=false那么S[i]则一定在子集中,那么我们就可以找到一个子集中的元素S[i]了。又因为S[i]在子集中,那么如果排除掉S[i],剩下的需要求的子集和就变成j-S[i],所以我就接着从dp[i-1][j]继续搜索子集中的元素了。

最后把这两块连起来:

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
vector<int> sum_problem(vector<int> nums, int target){
// init
vector<vector<bool> > dp(nums.size()+1, vector<bool> (target+1, false));
for (int i = 0; i < nums.size()+1; i++)
dp[i][0] = true;
// dp
for (int i = 1; i < nums.size()+1; i++){
for (int j = 1; j < target+1; j++){
if (j < nums[i-1])
dp[i][j] = dp[i-1][j];
else if (j - nums[i-1] >= 0)
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
vector<int> res;
if (!dp[nums.size()][target])
return res;
else
{
int sum = target;
while(sum != 0){
for (int i = nums.size(); i >= 1; i--){
if (dp[i][sum] == 1 && dp[i-1][sum] == 0){
res.push_back(i-1);
sum -= nums[i-1];
}
}
}
reverse(res.begin(), res.end());
return res;
}
}

参考资料

https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-xiang-jie-jin-jie
https://www.bilibili.com/video/av38722679

子集和问题:
https://www.cnblogs.com/yulinfeng/p/7106564.html
https://zhuanlan.zhihu.com/p/37822898