信用网站建设工作总结,o2o网站建设新闻,建设建行积分兑换商城网站,网站建设宣传ppt模板下载来源0x3f#xff1a;https://space.bilibili.com/206214 三叶姐的对背包问题的总结#xff1a;【宫水三叶】详解完全背包一维空间优化推导#xff08;附背包问题攻略#xff09;https://leetcode.cn/circle/discuss/GWpXCM/ 文章目录0-1背包、完全背包及其拓展#xff08;… 来源0x3fhttps://space.bilibili.com/206214 三叶姐的对背包问题的总结【宫水三叶】详解完全背包一维空间优化推导附背包问题攻略https://leetcode.cn/circle/discuss/GWpXCM/ 文章目录0-1背包、完全背包及其拓展选/不选思想的代表0-1背包常见变形【至多/恰好/至少】 ※重要纯0-1背包问题[494. 目标和](https://leetcode.cn/problems/target-sum/)记忆化搜索1:1翻译成递推动态规划空间优化滚动数组空间优化一个数组从后往前遍历背包完全背包变形纯完全背包问题[322. 零钱兑换](https://leetcode.cn/problems/coin-change/)记忆化搜索翻译成递推空间优化一维数组从前到后遍历背包练习[416. 分割等和子集](https://leetcode.cn/problems/partition-equal-subset-sum/)[279. 完全平方数](https://leetcode.cn/problems/perfect-squares/)[518. 零钱兑换 II](https://leetcode.cn/problems/coin-change-ii/)对边界条件的总结
不同的题目所要的答案不同 比如方案数最大、小值数字个数能否构成
这也就意味着 dp 数组值可以为数值也可以是 boolean 类型
另外同样是数值的情况下不同的要求也会造成不同的初始值 f【0】【0】 能否构成 f【0】【0】 True 0 可以构成 0 方案数 f【0】【0】 1 0 组成 0 只有一种方案 数字个数 f【0】【0】 0 0 组成 0 没有使用数字 最大、小值 问题一般会回归到 方案数 或 数字个数问题 一般会使用到 max/min 函数约束答案而且会使用 ±inf 初始化来表示极端情况。 比如力扣 279 求最小数量f【0】【j】 的初始值也是要考虑的 0-1背包、完全背包及其拓展选/不选思想的代表
0-1背包常见变形【至多/恰好/至少】 ※重要
1、至多装capacity求方案数/最大价值和
2、恰好装capacity求方案数/最大/最小价值和
3、至少装capacity求方案数/最小价值和
纯0-1背包问题
0-1背包问题有N件物品和一个容量为C的背包。第i件物品的费用是v[i]价值是w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量且价值总和最大。
dp[N][C1]解法
import java.util.Scanner;
public class Main{ public static void main(String[] args){ Scanner sc new Scanner(System.in); int N sc.nextInt(); int C sc.nextInt(); int[] v new int[N]; int[] w new int[N]; for (int i 0; i N; i){ v[i] sc.nextInt(); w[i] sc.nextInt(); }System.out.println(maxValue(N, C, v, w)); }private static int maxValue(int N, int C, int[] v, int[] w) {int[][] dp new int[N][C 1];dp[0][0] 0;//填充第 0 位物品在 0-C 容量下的初始值for (int i 0; i C 1; i) {dp[0][i] i v[0] ? w[0] : 0;}// 先遍历物品 再遍历背包for (int i 1; i N; i) {for (int j 0; j C 1; j) {int n dp[i - 1][j]; // 不选该物品int y 0;if (j v[i]) {y w[i] dp[i - 1][j - v[i]]; // 选择该物品}dp[i][j] Math.max(n, y);}}return dp[N - 1][C];}
}dp[2][C1]解法
private static int maxValue(int N, int C, int[] v, int[] w) {int[][] dp new int[2][C 1];dp[0][0] 0;for (int i 0; i C 1; i) {dp[0][i] i v[0] ? w[0] : 0;}for (int i 1; i N; i) {for (int j 0; j C 1; j) {int n dp[(i - 1)%2][j]; // 不选该物品int y 0;if (j v[i]) {y w[i] dp[(i - 1)%2][j - v[i]]; // 选择该物品}dp[i%2][j] Math.max(n, y);}}return dp[(N - 1)%2][C];}dp[C1]解法
private static int maxValue(int N, int C, int[] v, int[] w) {int[] dp new int[C 1];for (int i 0; i C 1; i) {dp[i] i v[0] ? w[0] : 0;}for (int i 1; i N; i) {for (int j C; j 0; j--) {int n dp[j]; // 不选该物品int y 0;if (j v[i]) {y w[i] dp[j - v[i]]; // 选择该物品}dp[j] Math.max(n, y);}}return dp[C];} 494. 目标和
难度中等1515
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 或 - 然后串联起所有整数可以构造一个 表达式
例如nums [2, 1] 可以在 2 之前添加 在 1 之前添加 - 然后串联起来得到表达式 2-1 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1
输入nums [1,1,1,1,1], target 3
输出5
解释一共有 5 种方法让最终目标和为 3 。
-1 1 1 1 1 3
1 - 1 1 1 1 3
1 1 - 1 1 1 3
1 1 1 - 1 1 3
1 1 1 1 - 1 3示例 2
输入nums [1], target 1
输出1提示
1 nums.length 200 nums[i] 10000 sum(nums[i]) 1000-1000 target 1000 从什么都不知道的题目到0-1背包问题的推理过程
设添加号的数和为p
则添加 - 号的数和为 sum-p
则 p-(sum-p) target p (st)/2 在nums中选择一些数字使得和恰好为p
记忆化搜索
class Solution {int[] nums;int[][] cache;public int findTargetSumWays(int[] nums, int target) {for(int x : nums) target x;if(target 0 || target % 2 1) return 0;target / 2;this.nums nums;int n nums.length;cache new int[n][target1];for (int i 0; i n; i)Arrays.fill(cache[i], -1); // -1 表示没用访问过return dfs(n - 1, target);}public int dfs(int i, int c){if(i 0) return c 0 ? 1 : 0;if(cache[i][c] ! -1) return cache[i][c];int res 0;if(c nums[i]) {res dfs(i-1, c); // 没有容量装下i位置的物体了}else{res dfs(i-1, c) dfs(i-1, c - nums[i]);}cache[i][c] res;return res;}
}1:1翻译成递推动态规划
class Solution {int[] nums;int[][] cache;public int findTargetSumWays(int[] nums, int target) {for(int x : nums) target x;if(target 0 || target % 2 1) return 0;target / 2;int n nums.length;int[][] f new int[n1][target1];f[0][0] 1; // 容量未0,所有数都选了for(int i 0; i n; i){for(int c 0; c target; c){if(c nums[i]){f[i1][c] f[i][c];}else{f[i1][c] f[i][c] f[i][c-nums[i]];}}}return f[n][target];}// public int dfs(int i, int c){// if(i 0) return c 0 ? 1 : 0;// if(cache[i][c] ! -1) return cache[i][c];// int res 0;// if(c nums[i]) {// res dfs(i-1, c); // 没有容量装下i位置的物体了// }else{// res dfs(i-1, c) dfs(i-1, c - nums[i]);// }// cache[i][c] res;// return res;// }
}空间优化滚动数组
(i1) (i1) % 2
class Solution {int[] nums;int[][] cache;public int findTargetSumWays(int[] nums, int target) {for(int x : nums) target x;if(target 0 || target % 2 1) return 0;target / 2;int n nums.length;int[][] f new int[2][target1];f[0][0] 1; // 容量未0,所有数都选了for(int i 0; i n; i){for(int c 0; c target; c){if(c nums[i]){f[(i1) % 2][c] f[i % 2][c];}else{f[(i1) % 2][c] f[i % 2][c] f[i % 2][c-nums[i]];}}}return f[n % 2][target];}
}空间优化一个数组从后往前遍历背包
从后往前遍历容量c
class Solution {int[] nums;int[][] cache;public int findTargetSumWays(int[] nums, int target) {for(int x : nums) target x;if(target 0 || target % 2 1) return 0;target / 2;int n nums.length;int[] f new int[target1];f[0] 1; // 容量未0,所有数都选了for(int i 0; i n; i){for(int c target; c nums[i]; c--){f[c] f[c] f[c-nums[i]];}}return f[target];}
}完全背包变形
纯完全背包问题
完全背包问题 有 N 种物品和一个容量为 C 的背包每种物品都有无限件。
第 i 件物品的体积是 v[i]价值是 w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量且价值总和最大。
其实就是在 0-1 背包问题的基础上增加了每件物品可以选择多次的特点在容量允许的情况下。
import java.util.Scanner;
public class Main{ public static void main(String[] args){ Scanner sc new Scanner(System.in); int N sc.nextInt(); int C sc.nextInt(); int[] v new int[N]; int[] w new int[N]; for (int i 0; i N; i){ v[i] sc.nextInt(); w[i] sc.nextInt(); }System.out.println(maxValue(N, C, v, w)); }private static int maxValue(int N, int C, int[] v, int[] w) {int[] dp new int[C 1];//先遍历物品再遍历背包for (int i 0; i N; i) {for (int j C; j v[i]; j--) {//比较格子的数量等于最多可选第i件物品多少次for (int k 0 ;; k) {if (j v[i] * k) {break;}dp[j] Math.max(dp[j], dp[j - v[i] * k] w[i] * k);}}}return dp[C];}
}完全背包的dp[C1]解法 private static int maxValue(int N, int C, int[] v, int[] w) {int[] dp new int[C 1];for (int i 0; i N; i) {// for (int j C; j v[i]; j--) { // 0-1 背包问题for (int j v[i]; j C; j) { // 完全背包问题int n dp[j]; // 不选该物品int y w[i] dp[j - v[i]]; // 选择该物品dp[j] Math.max(n, y);}}return dp[C];}
}
322. 零钱兑换
难度中等2307
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1
输入coins [1, 2, 5], amount 11
输出3
解释11 5 5 1示例 2
输入coins [2], amount 3
输出-1示例 3
输入coins [1], amount 0
输出0提示
1 coins.length 121 coins[i] 231 - 10 amount 104
记忆化搜索
class Solution {private int[] coins;private int[][] cache;public int coinChange(int[] coins, int amount) {this.coins coins;int n coins.length;cache new int[n][amount 1];for (int i 0; i n; i)Arrays.fill(cache[i], -1); // -1 表示没用访问过int ans dfs(n - 1, amount);return ans Integer.MAX_VALUE / 2 ? ans : -1;}private int dfs(int i, int c) {// 当 c0 时表示这是一个合法的方案if (i 0) return c 0 ? 0 : Integer.MAX_VALUE / 2; // 除 2 是防止下面 1 溢出if (cache[i][c] ! -1) return cache[i][c];if (c coins[i]) return cache[i][c] dfs(i - 1, c);return cache[i][c] Math.min(dfs(i - 1, c), dfs(i, c - coins[i]) 1);}
}翻译成递推
class Solution {public int coinChange(int[] coins, int amount) {int n coins.length;int[][] f new int[n 1][amount 1];Arrays.fill(f[0], Integer.MAX_VALUE / 2); // 除 2 是防止下面 1 溢出f[0][0] 0;for (int i 0; i n; i)for (int c 0; c amount; c)if (c coins[i]) f[i 1][c] f[i][c];else f[i 1][c] Math.min(f[i][c], f[i 1][c - coins[i]] 1);int ans f[n][amount];return ans Integer.MAX_VALUE / 2 ? ans : -1;}
}空间优化一维数组从前到后遍历背包
class Solution {public int coinChange(int[] coins, int amount) {int[] f new int[amount 1];Arrays.fill(f, Integer.MAX_VALUE / 2); // 除 2 是防止下面 1 溢出f[0] 0;for (int x : coins)for (int c x; c amount; c)f[c] Math.min(f[c], f[c - x] 1);int ans f[amount];return ans Integer.MAX_VALUE / 2 ? ans : -1;}
}练习
416. 分割等和子集
难度中等1645
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1
输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 。示例 2
输入nums [1,2,3,5]
输出false
解释数组不能分割成两个元素和相等的子集。提示
1 nums.length 2001 nums[i] 100
class Solution {// 每个元素只可以取一次元素的价值和大小就是自己本身public boolean canPartition(int[] nums) {Arrays.sort(nums);int sum 0;for(int num : nums) sum num;if(sum % 2 ! 0) return false;int target sum / 2; // 背包为target时有没有价值和为target(价值和只可能 target)int[] dp new int[target1]; // 空间优化一个数组for(int i 0; i nums.length; i){for(int j target; j nums[i]; j--){dp[j] Math.max(dp[j], dp[j-nums[i]] nums[i]);}}return dp[target] target ? true : false;}
}279. 完全平方数
难度中等1619
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
示例 1
输入n 12
输出3
解释12 4 4 4示例 2
输入n 13
输出2
解释13 4 9提示
1 n 104
朴素完全背包解法
class Solution {private static final int INF Integer.MAX_VALUE / 2;public int numSquares(int n) {// 将可能用到的【物品】预处理出来ListInteger list new ArrayList();for(int i 1; i * i n; i) list.add(i*i);// 问题就变成了给定数字中每个数字可以使用无限次求凑出目标值n所需要的最少数字个数是多少int[][] dp new int[list.size()1][n1]; // 前i个数字中凑出数字总和j所需要的最少数字个数//当没有任何数时除了 f[0][0] 为 0花费 0 个数值凑出 0其他均为无效值Arrays.fill(dp[0], INF); dp[0][0] 0;// dp[i][j] min(dp[i-1][j-k*t]k) 0 k*t j; k:选k个数字i第i个数字数值为tfor(int i 1; i list.size(); i){int x list.get(i-1);for(int j 0; j n; j){// 对于不选第 i 个数的情况dp[i][j] dp[i-1][j];// 对于选 k 次第 i 个数的情况for(int k 1; k * x j; k){// 能够选择 k 个 x 的前提是剩余的数字 j - k * x 也能被凑出if(dp[i-1][j-k*x] ! INF){dp[i][j] Math.min(dp[i][j], dp[i-1][j-k*x] k);}}}}return dp[list.size()][n];}
}空间优化
class Solution {private static final int INF Integer.MAX_VALUE / 2;public int numSquares(int n) {// 将可能用到的【物品】预处理出来ListInteger list new ArrayList();for(int i 1; i * i n; i) list.add(i*i);// 问题就变成了给定数字中每个数字可以使用无限次求凑出目标值n所需要的最少数字个数是多少int[] dp new int[n1]; // 前i个数字中凑出数字总和j所需要的最少数字个数//当没有任何数时除了 f[0][0] 为 0花费 0 个数值凑出 0其他均为无效值Arrays.fill(dp, INF); dp[0] 0;// dp[i][j] min(dp[i-1][j-k*t]k) 0 k*t j; k:选k个数字i第i个数字数值为tfor(int i 1; i list.size(); i){int x list.get(i-1);for(int j x; j n; j){dp[j] Math.min(dp[j], dp[j-x] 1);}}return dp[n];}
}518. 零钱兑换 II
难度中等1005
给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1
输入amount 5, coins [1, 2, 5]
输出4
解释有四种方式可以凑成总金额
55
5221
52111
511111示例 2
输入amount 3, coins [2]
输出0
解释只用面额 2 的硬币不能凑成总金额 3 。示例 3
输入amount 10, coins [10]
输出1提示
1 coins.length 3001 coins[i] 5000coins 中的所有值 互不相同0 amount 5000
class Solution {public int change(int amount, int[] coins) {int[] dp new int[amount1];dp[0] 1;for(int x : coins){for(int j x; j amount; j){dp[j] dp[j] dp[j-x];}}return dp[amount];}
}
