力扣爆刷第128天之动态规划五连刷（一个零、零钱兑换、组合）
文章目录
终结背包问题：这篇文章和上一篇。
动态规划解题步骤：
- 确定dp数组（dp table）以及下标的含义。
- 确定递推公式。
- dp数组如何初始化。
- 确定遍历顺序。
- 举例推导dp数组。
背包问题总结
背包问题：一维数组，dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i])。
01背包遍历顺序： 先物品后背包，物品正序，背包逆序。
如若背包正序则会出现同一个物品重复放入，如物品1重量为1，背包空间为1时放入了，背包空间为2时又放入了。
如果先背包后物品，为了避免重复放入背包依然是逆序，背包容量固定时，每种背包容量只能放入一个物品，即为最大的物品，小的物品都放不进来或者被覆盖了。
求组合数排列数：dp[j] += dp[j - nums[i]]
完全背包遍历顺序： 物品背包没有先后顺序，物品背包都是正序。因为同一个物品不限量可以放入多次，在背包采用正序中。
完全背包求组合数，物品在外，背包在内。求排列数，背包在外，物品在内。
一、474. 一和零
题目链接：https://leetcode.cn/problems/ones-and-zeroes/description/
思路：一和零是双重背包，本质上还是0 1 背包，只不过现在背包的容量有两个指标，所以还是0 1背包的套路，定义dp[i][j]数组表示容量为i个0和j个1的背包最多可以装下的字符串数量，故当前背包装物品的数量依赖于上一个容量较小时装的数量，具体是多少容量呢，当然是可以满足装下最大数量的容量，那到底是什么呢，就是例如有一个字符串有2个0和3个1，依赖于dp数组的定义，想让当前空间利用率最大，自然是把空间都占满，dp[i][j] = dp[i-2][j-3] + 1。故递推公式为dp[i][j] = Math.max(dp[i][j], dp[i-nums[0]][j-nums[1]] + 1);
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];
for(String s : strs) {
int[] nums = countNums(s);
for(int i = m; i >= nums[0]; i--) {
for(int j = n; j >= nums[1]; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i-nums[0]][j-nums[1]] + 1);
}
}
}
return dp[m][n];
}
int[] countNums(String s) {
int[] nums = new int[2];
int a = 0, b = 0;
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '0') {
a++;
}else{
b++;
}
}
nums[0] = a;
nums[1] = b;
return nums;
}
}
二、518. 零钱兑换 II
题目链接：https://leetcode.cn/problems/coin-change-ii/description/
思路：本题物品数量无限是完全背包，完全背包求组合数。完全背包物品和背包都是正序，如果求组合数，物品在外，背包在内。如果求排列数，背包在外，物品在内。
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount+1];
dp[0] = 1;
for(int i = 0; i < coins.length; i++) {
for(int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}
三、377. 组合总和 Ⅳ
题目链接：https://leetcode.cn/problems/combination-sum-iv/description/
思路：和上一题类似，也是物品无限使用，是完全背包，但是不同的是求的是排列数。物品和背包都正序，背包在外，物品在内。
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
dp[0] = 1;
for(int i = 1; i <= target; i++) {
for(int j = 0; j < nums.length; j++) {
if(nums[j] > i) continue;
dp[i] += dp[i - nums[j]];
}
}
return dp[target];
}
}
四、57. 爬楼梯（第八期模拟笔试）
题目链接：https://kamacoder.com/problempage.php?pid=1067
思路：本题是总楼梯数是背包总数，每次可以爬的楼梯数（1 <= m < n），求有多少种爬楼的方法。所以很明显是完全背包求排列数，爬楼梯的方法1,2和2,1明细是两种方法。所以直接套公式，完全背包求排列数，背包在外，物品在内。背包和物品都正序。
同时推荐一下卡码网，可以练习ACM模式。
import java.lang.*;
import java.util.*;
class Main{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt(), m = scan.nextInt();
int[] dp = new int[n+1];
dp[0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(i >= j) {
dp[i] += dp[i-j];
}
}
}
System.out.println(dp[n]);
}
}
五、322. 零钱兑换
题目链接：https://leetcode.cn/problems/coin-change/description/
思路：本题是物品数量无限，完全背包。对于完全背包求组合数，物品在外，背包在内，求排列数，背包在外，物品在内。
其他的比如求能装的最大最小个数，物品和背包没有顺序要求，所以在内在外都行，其他的没有了。
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 0; i < coins.length; i++) {
for(int j = coins[i]; j <= amount; j++) {
if(dp[j-coins[i]] == Integer.MAX_VALUE) continue;
dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
