【每日算法Day 58】DP强化理解2
这次来看一下最优子结构、dp数组遍历方向以及dp数组状态压缩的问题。
最优子结构并不是动态规划独有的性质，能求最值的问题大部分有该性质。但该性质是动态规划问题的必要条件，找最优子结构的过程其实就是证明状态转移方程正确性的过程。根据找到的最优子结构写出暴力递归的方程就能看出有没有重叠子问题了，如果有就需要通过记忆化的方式进行优化。
另外关于动态规划中dp数组的遍历方向的问题，我们只需要明确两点：
- base case在哪里？
- 遍历的终点（要求的最终的最优解）在哪里？
由于遍历过程中所有的状态必须是已经计算出来的，所以只需要确保总体的方向是从base case到终点就可以了。
# LeetCode 416. 分割等和子集（子集背包问题） (opens new window)
# 题目描述
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100 ， 数组的大小不会超过 200
# 示例
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
2
3
4
5
# 解题思路
该问题似乎不是一个明显的背包问题，但我们可以这样把问题转换为：给出一个可装载重量为sum/2的背包和n个物品，每个物品重量为nums[i]，是否存在一种装法能将背包恰好装满？
那么该问题的状态就是：背包的总容量和可选择的物品，选择就是：选用第i个物品或不选用第i个物品。可以将dp[i][j]定义为：在前i个物品中是否有一种组合总容量达到j。如果不选择当前第i个物品，则dp[i][j]=dp[i-1][j]，如果选择第i个物品，则dp[i][j]=dp[i-1][j-nums[i]] (nums[i]<=j)。这就是该问题的状态转移方程。
再来看问题的边界case，背包容量为0的时候不取物品总能将背包装满，dp[i][0]=true；除此之外前0个物品总不能装满背包，dp[0][i]=false。
public boolean canPartition(int[] nums) {
int sum = 0;
for (int i : nums) {
sum += i;
}
if ((sum & 1) == 1) return false;
int m = nums.length, n = sum / 2;
boolean[][] dp = new boolean[m + 1][n + 1];
for (int i = 0; i <= n; i++) {
dp[0][i] = false;
}
for (int i = 0; i <= m; i++) {
dp[i][0] = true;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <=n ; j++) {
dp[i][j] = dp[i - 1][j] || (nums[i - 1] <= j && dp[i - 1][j - nums[i - 1]]);
}
}
return dp[m][n];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
我们发现状态转移时，每次只使用了上一行中上方和左侧的值，因此可以进行状态压缩，采用一维dp数组就可以了。因为使用的是上方和左上方的值，因而内层循环要从右往左更新。
public boolean canPartition(int[] nums) {
int sum = 0;
for (int i : nums) {
sum += i;
}
if ((sum & 1) == 1) return false;
int m = nums.length, n = sum / 2;
boolean[] dp = new boolean[n + 1];
dp[0]=true;
for (int i = 1; i <= m; i++) {
for (int j = n; j >=0 ; j--) {
dp[j] = dp[j] || (j - nums[i-1] >= 0 && dp[j - nums[i-1]]);
}
}
return dp[n];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
该解法的时间复杂度 O(n*sum)，空间复杂度 O(sum)。
# LeetCode 518. 零钱兑换 II (opens new window)
# 题目描述
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
你可以假设：
0 <= amount (总金额) <= 5000； 1 <= coin (硬币面额) <= 5000； 硬币种类不超过 500 种； 结果符合 32 位符号整数；
# 示例
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
2
3
4
5
6
7
# 解题思路
根据问题这一题的dp[i][j]可以用来表示使用前i个种硬币能凑成金额j时的组合数，那么对于第i种硬币，要么之前i-1种不使用它就已经凑成金额j（dp[i-1][j]），要么之前已经使用它并凑成j-coin[i-1]（dp[i][j-coin[i-1]，这里coin是从0开始的所以为i-1）。
public int change(int amount, int[] coins) {
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= amount; j++) {
dp[i][j]=dp[i-1][j];
if (j-coins[i-1]>=0)
dp[i][j] += dp[i][j - coins[i - 1]];
}
}
return dp[n][amount];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
和上一题状态压缩时有所不同，这里需要用到上一行当前位置的值和本行当前位置左侧的已经计算过的值，所以进行状态压缩时，本行左侧的值需要先计算，因此内层循环依然是从左向右。
public int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= amount; j++) {
if (j-coins[i-1]>=0)
dp[j] += dp[j - coins[i - 1]];
}
}
return dp[amount];
}
2
3
4
5
6
7
8
9
10
11
12