动态规划背包问题
目录
分割等和子集
416. 分割等和子集 - 力扣（LeetCode）416. 分割等和子集 - 力扣（LeetCode）
在解决该问题时，若直接尝试将数组拆分成两个子集，难度较大，因此需要转换思维方式。本题的关键在于“将数组分割成两个子集，使两个子集的元素和相等”。假设原始数组的总和为sum，那么两个子集的元素和必然都为sum/2 。分析到这一步就会发现，只需解决其中一个子集的问题即可。由于总和sum是固定不变的，若一个子集的和为sum/2，那么另一个子集的和自然也是sum/2 。于是，当前问题就转变为从一个数组中选取部分元素，使其和等于sum/2。
这其实就是一个01背包问题。01背包问题是指给定一些物品，每个物品仅有一个，对于每个物品都面临选或不选的抉择，然后在背包承重能力范围内挑选物品，以追求最大价值。而本题是将数组中的每个数视为一个物品，把sum/2当作背包的容量，每个物品同样面临选或不选的情况，目标是恰好装满这个背包。与常规01背包问题不同的是，本题中物品只有体积，没有价值，我们只需将背包装满就行。
1. 状态表示
dp[i][j] 中，i表示从前i个数中进行选择，dp[i][j]表示在所有这些选法中能否凑出和为j的情况。这里dp是boolean类型，若能凑出和为j则为true，否则为false。
2. 状态转移方程
从最后一步进行推导，dp[i][j] 可分为两种情形：
第一种情形：不选择第i个数，此时只需知道从前i - 1个数中能否凑出和为j，所以dp[i][j] = dp[i - 1][j]。
第二种情形：选择第i个数，那么当前已选定了一个数nums[i]，接下来只需从前i - 1个数中选出和为j - nums[i] 的组合。这里需要注意，j - nums[i] 不一定存在，若nums[i] 过大，j - nums[i] 会是负数。所以要添加判定条件j >= nums[i] ，此时dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]] ，这两种情况只要有一种成立即可。
3. 初始化
为避免越界，初始化时在最上面添加一层，最左侧添加一列虚拟节点，同时要特别留意下标映射关系。第一行代表数组为空的情况，要凑出和为0、1、2…… ，显然在数组为空时，只能凑出和为0（什么都不选和即为0），所以第一行只有一处为true，其余均为false。而第一列表示无论选择哪些数，都可以通过什么都不选来凑出和为0，所以第一列全为true。综合来看，初始化时只需将第一列初始化为true即可。
4. 填表顺序
i必然是从上往下依次填充，j也需要先求出前面的值，所以同样是从上往下填充。
5. 返回值
要从前n个数中选择出和为sum/2的情况，即返回dp[n][sum/2] 。需要注意的是，如果在计算出sum后，发现sum % 2 == 1 ，说明sum是奇数，这种情况下无法将数组分割成两个元素和相等的子集，应直接返回false。
class Solution {
public boolean canPartition(int[] nums) {
// 计算数组总和
int sum = 0, n = nums.length;
for(int i : nums) sum += i;
// 如果总和是奇数，直接返回false，因为无法平分
if(sum % 2 == 1) return false;
// 目标是找到和为总和一半的子集
int aim = sum / 2;
// 创建动态规划表
// dp[i][j]表示前i个数字中能否选出若干数字使其和为j
boolean[][] dp = new boolean[n + 1][aim + 1];
// 初始化：和为0的情况总是可以达成（不选任何数字）
for(int i = 0; i <= n; i++) dp[i][0] = true;
// 动态规划填表
for(int i = 1; i <= n; i++){
for(int j = 1; j <= aim; j++){
// 默认不选当前数字，看前i-1个数字能否达到j
dp[i][j] = dp[i - 1][j];
// 如果当前数字nums[i-1]小于等于j，考虑选它的情况
if(j >= nums[i - 1]){
// 当前结果 = 不选当前数字 或 选当前数字（看前i-1个数字能否达到j-nums[i-1]）
dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
// 返回前n个数字能否选出和为aim的子集
return dp[n][aim];
}
}在01背包问题的常规解法中，通常使用二维数组`dp[i][j]`来记录状态。然而，这种方法存在一定的空间优化空间。可以把01背包的优化就是将所有的行删除，修改第二层修改的遍历顺，其核心思路是利用一维数组来替代二维数组，从而降低空间复杂度。
原本的二维数组dp[i][j]，其中i代表考虑前i个物品，j代表背包容量为j时的状态。在状态转移方程中，可以观察到dp[i][j]的取值仅依赖于dp[i - 1][j]和dp[i - 1][j - nums[i]]，也就是说，当前行的状态只与上一行的状态有关。
具体优化过程如下：将二维数组dp改为一维数组dp[j]，这里的j依然表示背包容量。在进行状态转移时，由于dp[j]的更新会依赖于dp[j - nums[i]]，如果仍然按照从小到大的顺序遍历j，那么在更新dp[j]时，dp[j - nums[i]]可能已经是被当前物品i更新后的状态，而不是上一个物品i - 1对应的状态，这样就会导致错误的结果。所以，我们需要修改第二层遍历的顺序，将其改为从大到小遍历。这样，在更新dp[j]时，dp[j - nums[i]]还未被当前物品`i`更新，保证了状态转移的正确性。
例如，对于一个物品数组nums和背包容量sum/2，在使用一维数组优化时，我们先初始化dp[0]为true，表示背包容量为0时可以被凑出。然后，对于每个物品nums[i]，从sum/2开始，以递减的方式遍历到nums[i]。在遍历过程中，对于每个j，如果dp[j - nums[i]]为true，则说明可以通过选择当前物品nums[i]来凑出背包容量j，此时将dp[j]也设为true。
class Solution {
public boolean canPartition(int[] nums) {
// 计算数组总和
int sum = 0, n = nums.length;
for (int i : nums) sum += i;
// 如果总和为奇数，无法平分，直接返回false
if (sum % 2 == 1) return false;
// 目标子集和（背包容量）
int aim = sum / 2;
// 初始化动态规划数组：dp[j]表示能否凑出和为j的子集
boolean[] dp = new boolean[aim + 1];
dp[0] = true; // 初始状态：和为0的子集（不选任何元素）总是存在
// 动态规划填表
for (int i = 1; i <= n; i++) {
// 逆向遍历背包容量，避免重复计算（01背包特性）
for (int j = aim; j >= 0; j--) {
// 保留不选当前元素时的状态
dp[j] = dp[j];
// 如果当前元素可以放入背包（j >= nums[i-1]）
if (j >= nums[i - 1]) {
// 状态转移：选或不选当前元素，只要有一种情况成立即可
dp[j] = dp[j] || dp[j - nums[i - 1]];
}
}
}
// 检查是否能凑出目标和aim
return dp[aim];
}
}目标和
在处理该问题时，若直接采用动态规划方法，状态表示的构思以及状态转移方程的推导都极具挑战性，因此需要对问题进行转换。
假设有一组数构成集合x，将集合x里的数划分为两类，一类全是正数，另一类全是负数。设所有正数之和为a，所有负数的绝对值之和为b，那么目标值target等于a减去b。至此，问题转变为把集合x中的数分成两堆，求使得左边一堆减去右边一堆结果为target的分法有多少种。然而，这种两堆划分的问题依旧不易解决。
我们继续转换思路，考虑所有元素的总和sum。已知a - b = target且a + b = sum，通过这两个等式消去b，可得出a = (target + sum) / 2。此时，由于a能够计算得出，就无需再考虑b。问题进一步简化为在整个集合x中挑选出一些数，使这些数的和等于a，并统计挑选的方法总数。
经过这样的转换可以发现，该问题实际上就是01背包问题。从这些数中挑选数时，每个数都面临选或不选的情况，且要让挑选出的数的和等于a，这类似于在01背包问题中挑选物品放入背包，使背包恰好装满。
1. 状态表示，定义dp[i][j]，其中i代表从前i个元素中进行选择，j表示所选元素总和正好等于j，此时dp[i][j]表示这种情况下的选法总数。
2. 状态转移方程存在两种情形：第一种，若不选择i位置处的值，那么dp[i][j]等于dp[i - 1][j]，因为不选当前位置的数，从前i个数中选且和为j的选法数量与从前i - 1个数中选且和为j的选法数量相同。第二种，若选择i位置处的值，dp[i][j]等于dp[i - 1][j - nums[i]]，因为要使总和凑成j，且i位置的数是必选的，这就相当于从前i - 1个数中挑选出总和为j - nums[i]的选法数量。综合起来，dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]，不过要注意，只有在j大于等于nums[i]的情况下，dp[i - 1][j - nums[i]]才存在，才能进行此计算。
3. 初始化时，如同上一题一样添加最上面和最左边的虚拟层，并留意下标映射关系。第一行表示从没有数即数值都为0的情况下凑成和为0、1、2、3、4等的情况，此时仅能凑成和为0，即啥都不选，所以dp[0][0]为1，而dp[0][j]（j大于0）为0。第一列表示从前i个元素中选择凑成总和为0的情况，由于数组中的值可能为0，若直接初始化第一列会很复杂，因为若某个位置的数为0，其可选个数情况较多。实际上这里可以不初始化，因为初始化第一列主要是为了在使用时防止越界，而这里只有在j大于等于nums[i]时才会用到dp[i - 1][j - nums[i]]。当j为0即第一列时，要使0大于等于nums[i]成立且用到该状态，那么nums[i]必须为0，此时j - nums[i]为0，依旧使用的是上一个状态，不会出现越界访问的情况，所以第一列可在填表过程中自行填充。
4. 填表顺序上，因为填写当前状态dp[i][j]时，只要保证其上方的dp[i - 1][j]和左上方的dp[i - 1][j - nums[i]]已更新即可，所以是从上往下进行填表。
5. 返回结果，最终返回值为dp[n][a]，它表示从n个元素之前的所有元素中挑选出和为a的总选法数量。
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// 计算数组总和
int n = nums.length, sum = 0;
for(int x : nums) sum += x;
// 将问题转化为子集和问题
// 设正数子集和为P，负数子集和为N，则P - N = target且P + N = sum
// 解得P = (target + sum)/2
int aim = (target + sum) / 2;
// 处理不可能情况：
// 1. aim为负数（因为所有数都是非负的）
// 2. (target + sum)不是偶数（因为需要被2整除）
if(aim < 0 || (target + sum) % 2 == 1) return 0;
// 初始化动态规划数组
// dp[i][j]表示前i个元素中选出若干个数使其和为j的方法数
int[][] dp = new int[n+1][aim + 1];
// 基本情况：前0个元素和为0有1种方法（什么都不选）
dp[0][0] = 1;
// 填充dp表
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= aim; j++) {
// 默认不选当前数字
dp[i][j] = dp[i - 1][j];
// 如果当前数字可以被选中（j >= nums[i-1]）
if(j >= nums[i - 1]) {
// 加上选当前数字的情况
dp[i][j] += dp[i - 1][j - nums[i - 1]];
}
}
}
// 返回前n个元素中选出若干个数使其和为aim的方法数
return dp[n][aim];
}
}优化，01背包优化就是删除所有行，内层循环采用逆序遍历，这是为了避免重复计算同一个数字多次。正序遍历会导致同一个数字被多次使用，而逆序遍历保证了每个数字只被使用一次
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// 计算数组总和
int n = nums.length, sum = 0;
for(int x : nums) sum += x;
// 将问题转化为子集和问题：
// 设正数子集和为P，负数子集和为N，则P - N = target且P + N = sum
// 解得P = (target + sum)/2
int aim = (target + sum) / 2;
// 处理不可能情况：
// 1. aim为负数（因为所有数都是非负的）
// 2. (target + sum)不是偶数（因为需要被2整除）
if(aim < 0 || (target + sum) %2 == 1) return 0;
// 初始化动态规划数组
// dp[j]表示和为j的子集数目
int[] dp = new int[aim + 1];
// 基本情况：和为0的子集只有空集一种情况
dp[0] = 1;
// 动态规划填充过程
for(int i = 1; i <= n; i++ ){
// 逆序遍历，避免重复计算
for(int j = aim; j >= nums[i - 1]; j--){
// 状态转移方程：
// 当前数字nums[i-1]可以选择加入子集或不加入
// 如果加入，那么dp[j] += dp[j - nums[i-1]]
// 如果不加入，dp[j]保持不变
dp[j] += dp[j - nums[i - 1]];
}
}
// 返回和为aim的子集数目
return dp[aim];
}
}最后一块石头的重量II
1049. 最后一块石头的重量 II - 力扣（LeetCode）
和上一题类似，直接求解本题难度较大，因此需要转换思路。
假设有一组数构成集合x，我们把集合x中的数划分为两类，一类全是正数，另一类全是负数。设所有正数的总和为a，所有负数的绝对值总和为b。题目要求的是最后一块石头的重量，也就是要让|a - b|尽可能小。由于正负号可以相互转换，不妨假设a≤b，那么我们要求的就是b - a的最小值。
已知a + b = sum，现在已知两数之和为sum，需要找出差值最小的两个数。例如，对于数字9，可以拆分为1和8、2和7、3和6、4和5等组合，能发现这两个数越接近9的一半，它们的差值就越小。
于是，问题转化为在数组中选择一些数，使这些数的和尽可能接近sum/2。
这实际上是一道01背包问题。将所有数看作物品，每个物品都有选或不选的可能。把所有数的值既当作体积nums[i]，也当作价值nums[i]，而背包的总容量设定为sum/2。这样一来，该问题与01背包问题完全一致，即从一些数中选择放入背包，在不超过背包容量sum/2的前提下，让背包的价值最大化。要实现价值最大化，背包必然要尽可能装满，相应地体积也会增大。所以，问题本质就是选择一些数，使背包尽可能装满，也就是让价值达到最大。
1. 状态表示：定义dp[i][j]，其中i表示从前i个物品中选择一些数，j表示这些数的总和不超过j时能达到的最大和。
2. 状态转移方程：依据是否选择第i个物品，可分为两种情况。
- 第一种情况，若不选择第i个物品，那么dp[i][j]与上一个状态相同，即dp[i][j] = dp[i - 1][j]。
- 第二种情况，若选择第i个物品，这意味着当前已经有了数值nums[i]，此时需要从前i - 1个物品中挑选出总和为j - nums[i]的数。所以有dp[i][j] = dp[i - 1][j - nums[i]] + nums[i]。需要注意的是，只有当j大于等于nums[i]时，dp[i - 1][j - nums[i]]才存在。综合两种情况，为了取最大值，dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])。
3. 初始化：与以往类似，添加虚拟层。根据上一题的分析，第一列无需初始化，仅需初始化第一行。当j = 0时，第一行表示在没有石头的情况下，想要凑成总和为0、1、2……的最大价值均为0，由于新创建的对象初始值为0，所以此处无需额外初始化，仅需留意映射关系即可。
4. 填表顺序：填表顺序是从上往下进行。
5. 返回结果：dp[n][sum/2]表示从前n个数中选择，总和不超过sum/2的最大和，这个值即为a。而b = sum - dp[n][sum/2]，那么所求的最小值为b - a = sum - 2 * dp[n][sum/2]。
class Solution {
public int lastStoneWeightII(int[] stones) {
int n = stones.length, sum = 0;
// 计算所有石头的总重量
for(int x : stones) sum += x;
// 目标是将石头分成两堆，使两堆的重量差最小
// 转化为背包问题：找一个子集，使其和最接近sum/2
int aim = sum / 2;
// dp[i][j]表示前i个石头中选出若干石头，总重量不超过j的最大重量
int[][] dp = new int[n+1][aim+1];
// 动态规划填表
for(int i = 1; i <= n; i++){ // 遍历每个石头
for(int j = 0; j <= aim; j++){ // 遍历每个可能的重量
// 不选当前石头
dp[i][j] = dp[i - 1][j];
// 如果当前石头的重量不超过j，考虑选它
if(j >= stones[i - 1])
// 选当前石头或不选，取较大值
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
}
}
// 最终结果是总重量减去两倍的最接近sum/2的子集和
// 因为sum - dp[n][aim]是另一堆的重量，差值为(sum - dp[n][aim]) - dp[n][aim]
return sum - 2 * dp[n][aim];
}
}优化：
class Solution {
public int lastStoneWeightII(int[] stones) {
int n = stones.length, sum = 0;
// 计算所有石头的总重量
for(int x : stones) sum += x;
// 目标是将石头分成两堆，使两堆的重量差最小
// 转化为背包问题：找一个子集，使其和最接近sum/2
int aim = sum / 2;
// 使用一维数组优化空间复杂度
// dp[j]表示在不超过重量j的情况下能获得的最大重量
int[] dp = new int[aim+1];
// 动态规划填表
for(int i = 1; i <= n; i++){ // 遍历每个石头
// 逆序遍历，避免重复计算
for(int j = aim; j >= stones[i - 1]; j--){
// 更新dp[j]：选当前石头或不选，取较大值
dp[j] = Math.max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
}
}
// 最终结果是总重量减去两倍的最接近sum/2的子集和
// 因为sum - dp[aim]是另一堆的重量，差值为(sum - dp[aim]) - dp[aim]
return sum - 2 * dp[aim];
}
}[模板]完全背包
所有的背包问题都是以01背包为基础的，01背包是每一个物品都只能选一个或不选。完全背包就是一个物品可以挑选多次或不选。
1. 状态表示：
第一问：dp[i][j]表示从前i个物品中挑选，总体积不超过j，所有选法中的最大价值。
第二问：dp[i][j]表示从前i个物品中挑选，总体积等于j，所有选法中的最大价值。
2. 状态转移方程：由于每一个物品可以挑选多次，因此有很多种挑法，如果一个都不选，或者选择一个，或者选择两个，三个可以不限次数的选
当一个都不选时：dp[i][j] = dp[i-1][j]
当只选择一个时：dp[i][j] = dp[i-1][j - v[i]] + v[i]
当只选择两个时：dp[i][j] = dp[i-1][j -2* v[i]] + 2*v[i]
当只选择两个时：dp[i][j] = dp[i-1][j -3* v[i]] + 3*v[i]...依次类推
优化后的状态转移方程即为
第一问：dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])，和01背包一样j-v[i]可能不存在由此要进行判断。
第二问：规定用-1表示不能凑成该状态，用上面公式时还要进行判断dp[i][j-v[i]]!=-1
3. 初始化：增加虚拟节点，第一列的节点不用进行初始化，在进行循环填表时进行填入即可，第一行表示没有物品，当没有物品时想凑成体积小于等于0，1，2，3...时，只能凑成0，啥都不选即可，但是价值也有0，所以全都初始化0即可。综上不用进行初始化
第二问：第一行，是必须要凑成0，1，2，3...时，只能凑成0，则0位置初始化为0，其他位置由于都凑不成所以初始化为-1
4. 填表顺序：和01背包一样是从上向下填填写每一行，但是因为要用到当前元素的左边的元素所以每一行要从左往右进行填表。
5. 返回值：根据状态表示可值返回dp[n][v]从前n的元素中挑选出总体积不超过v.
第二问：当dp[n][v]等于-1时要返回0
import java.util.Scanner;
public class Main {
// 定义最大容量，避免数组越界
private static final int N = 1010;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 读取物品数量n和背包容量V
int n = in.nextInt();
int V = in.nextInt();
// v[i]表示第i个物品的体积，w[i]表示第i个物品的价值
int[] v = new int[N];
int[] w = new int[N];
// 读取每个物品的体积和价值，注意下标从1开始
for(int i = 1; i <= n; i++){
v[i] = in.nextInt();
w[i] = in.nextInt();
}
// ========== 第一问：完全背包问题的最大价值 ==========
// dp[i][j]表示前i个物品，背包容量为j时的最大价值
int[][] dp = new int[N][N];
// 根据状态转移方程进行填表
for(int i = 1; i <= n; i++){ // 遍历每个物品
for(int j = 0; j <= V; j++){ // 遍历每种背包容量
// 默认不选第i个物品
dp[i][j] = dp[i-1][j];
// 如果当前容量j可以放下第i个物品
if(j >= v[i]){
// 比较不选当前物品和选当前物品的较大值
// 注意这里是dp[i][j-v[i]]，因为可以重复选择
dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
}
// 输出最大价值
System.out.println(dp[n][V]);
// ========== 第二问：恰好装满背包的最大价值 ==========
// 重新初始化dp数组
dp = new int[N][N];
// 初始化条件：容量为0时价值为0，其他初始为-1表示不可达
for(int i = 1; i <= V; i++){
dp[0][i] = -1; // 前0个物品无法装满任何非零容量
}
// 根据状态转移方程进行填表
for(int i = 1; i <= n; i++){ // 遍历每个物品
for(int j = 0; j <= V; j++){ // 遍历每种背包容量
// 默认不选第i个物品
dp[i][j] = dp[i-1][j];
// 如果当前容量j可以放下第i个物品，且j-v[i]的状态可达
if(j >= v[i] && dp[i][j-v[i]] != -1){
// 比较不选当前物品和选当前物品的较大值
dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
}
// 输出结果：如果可达则输出最大值，否则输出0
if(dp[n][V] != -1)
System.out.println(dp[n][V]);
else
System.out.println(0);
}
}优化：使用滚动数组进行优化时，要注意01背包是为了避免覆盖前面的值从右向左遍历，而这里是因为要用到前面的状态所以必须从左向右进行遍历。这里使用-0x3f3f3f3f表示不可达状态，只有在状态可达时候才会进行状态转移方程。
import java.util.Scanner;
import java.util.Arrays;
public class Main {
private static final int N = 1010;
private static final int INF = -0x3f3f3f3f;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int V = in.nextInt();
int[] v = new int[N];
int[] w = new int[N];
for(int i = 1; i <= n; i++){
v[i] = in.nextInt();
w[i] = in.nextInt();
}
// 第一问：普通完全背包
int[] dp = new int[N];
for(int i = 1; i <= n; i++){
for(int j = v[i]; j <= V; j++){
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
System.out.println(dp[V]);
// 第二问：恰好装满的完全背包
dp = new int[N];
Arrays.fill(dp, INF); // 初始化为不可达
dp[0] = 0; // 容量0时价值0
for(int i = 1; i <= n; i++){
for(int j = v[i]; j <= V; j++){
if(dp[j - v[i]] != INF){ // 只有前驱状态可达才转移
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
System.out.println(dp[V] == INF ? 0 : dp[V]);
}
}零钱兑换
1. 状态表示：dp[i][j]表示从前i个硬币中挑选，总和等于j，所有选法中的最小硬币数。
2. 状态转移方程：由于每一个物品可以挑选多次，因此有很多种挑法，如果一个都不选，或者选择一个，或者选择两个，三个可以不限次数的选
当一个都不选时：dp[i][j] = dp[i-1][j]
当只选择一个时：dp[i][j] = dp[i-1][j - coins[i -1 ]] + 1
当只选择两个时：dp[i][j] = dp[i-1][j -2*coins[i -1 ]] +2
当只选择两个时：dp[i][j] = dp[i-1][j -3* coins[i -1 ]] + 3..依次类推
优化后的状态转移方程即为 dp[i][j - coins[i]] + 1
规定用-1表示不能凑成该状态，用上面公式时还要进行判断dp[i][j-coins[i -1 ]]!=-1
3. 初始化：增加虚拟节点，第一列的节点不用进行初始化，在进行循环填表时进行填入即可
第一行，是必须要凑成0，1，2，3...时，此时只能凑成0，则0位置初始化为0，其他位置由于都凑不成所以初始化为0x3f3f3f3f表示无穷大，为无效值，填表时候不可用
4. 填表顺序：从上向下填填写每一行，但是因为要用到当前元素的左边的元素所以每一行要从左往右进行填表。
5. 返回值：当dp[n][amount],但是如果>=0x3f3f3f3f则表示无法凑成amount返回-1。
class Solution {
public int coinChange(int[] coins, int amount) {
// 硬币种类数
int m = coins.length;
// 定义一个足够大的数表示"无穷大"（不可达状态）
final int INF = 0x3f3f3f3f;
// dp[i][j]表示用前i种硬币凑出金额j所需的最少硬币数
int[][] dp = new int[m+1][amount+1];
// 初始化：0个硬币时，除了amount=0，其他金额都不可达（INF）
for(int i = 1; i <= amount; i++) {
dp[0][i] = INF; // 没有硬币可用时，任何非零金额都无法凑出
}
for(int i = 1; i <= m; i++) { // 遍历每种硬币
for(int j = 0; j <= amount; j++) { // 遍历每个目标金额
// 初始状态：不选当前硬币时的解
dp[i][j] = dp[i-1][j];
// 如果当前金额j >= 当前硬币面值，可以考虑选择该硬币
if(j >= coins[i-1]) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-coins[i-1]] + 1);
}
}
}
// 最终结果：如果dp[m][amount]仍为INF，说明无法凑出，返回-1
return dp[m][amount] >= INF ? -1 : dp[m][amount];
}
}优化版本
class Solution {
public int coinChange(int[] coins, int amount) {
// 硬币种类数
int m = coins.length;
// 定义一个足够大的数表示"无穷大"（不可达状态）
final int INF = 0x3f3f3f3f;
int[] dp = new int[amount+1];
// 初始化：0个硬币时，除了amount=0，其他金额都不可达（INF）
for(int i = 1; i <= amount; i++) {
dp[i] = INF; // 没有硬币可用时，任何非零金额都无法凑出
}
for(int i = 1; i <= m; i++) { // 遍历每种硬币
// 遍历每个目标金额 注意因为要用到本行的状态所以从左向右遍历
for(int j = coins[i-1]; j <= amount; j) {
//只有可达状态才进行状态转移方程
if(dp[j - coins[i-1]] != INF){
dp[j] = Math.min(dp[j], dp[j-coins[i-1]] + 1);
}
}
}
// 最终结果：如果dp[amount]仍为INF，说明无法凑出，返回-1
return dp[amount] >= INF ? -1 : dp[amount];
}
}零钱兑换II
1. 状态表示：dp[i][j]表示从前i个硬币中挑选，总和等于j，所有选法中的硬币组合数。
2. 状态转移方程：由于每一个物品可以挑选多次，因此有很多种挑法，如果一个都不选，或者选择一个，或者选择两个，三个可以不限次数的选
当一个都不选时：dp[i][j] = dp[i-1][j]
当只选择一个时：dp[i][j] = dp[i-1][j - coins[i -1 ]] 需要注意，这里计算的是组合数，因此无需将单个组合内的硬币数量相加，因为增加单个组合内的硬币数量，并不会产生新的组合。
当只选择两个时：dp[i][j] = dp[i-1][j -2*coins[i -1 ]]
当只选择两个时：dp[i][j] = dp[i-1][j -3* coins[i -1 ]]..依次类推
优化后的状态转移方程即为 dp[i][j - coins[i]]
即dp[i][j] = dp[i-1][j] + dp[i][j - coins[i]]
3. 初始化：增加虚拟节点，第一列的节点不用进行初始化，在进行循环填表时进行填入即可
第一行，是必须要凑成0，1，2，3...时，此时只能凑成0，则组合数为1，其他位置由于都凑不成所以初始化为0即可，表示没有选法。
4. 填表顺序：从上向下填填写每一行，但是因为要用到当前元素的左边的元素，所以每一行要从左往右进行填表。
5. 返回值：当dp[n][amount]。
class Solution {
public int change(int amount, int[] coins) {
// 硬币种类数
int n = coins.length;
// dp[i][j]表示使用前i种硬币凑成金额j的组合数
int[][] dp = new int[n + 1][amount + 1];
// 初始化：凑成金额0的组合数为1（即不使用任何硬币）
dp[0][0] = 1;
// 根据状态转移方程填表
for (int i = 1; i <= n; i++) { // 遍历每种硬币
for (int j = 0; j <= amount; j++) { // 遍历每个目标金额
// 初始状态：不使用当前硬币时的组合数
dp[i][j] = dp[i - 1][j];
// 如果当前金额j >= 当前硬币面值，可以考虑使用该硬币
if (j >= coins[i - 1]) {
// 状态转移方程：总组合数 = 不使用当前硬币的组合数 + 使用当前硬币的组合数
dp[i][j] += dp[i][j - coins[i - 1]];
}
}
}
// 返回使用所有硬币凑成目标金额的组合数
return dp[n][amount];
}
}优化版本：
class Solution {
public int change(int amount, int[] coins) {
// 硬币种类数
int n = coins.length;
// dp数组：dp[j]表示凑成金额j的组合数
int[] dp = new int[amount + 1];
// 初始化：凑成金额0的组合数为1（即不使用任何硬币）
dp[0] = 1;
// 动态规划填表过程
for (int x : coins) { // 遍历每种硬币
// 从当前硬币面值开始遍历，避免不必要的判断
for (int j = x; j <= amount; j++) {
// 状态转移方程：
// dp[j] = 不使用当前硬币的组合数（原值） + 使用当前硬币的组合数
dp[j] += dp[j - x];
}
}
// 返回最终结果
return dp[amount];
}
}完全平方数
该题就是从n的数中挑选几个完全平方数，使这几个完全平方数和为n，一个完全平方数可以挑选多次。此时就发现就是完全背包问题，需要注意在创建dp表时，行不要创建成n，只要初始化为n的根号即可，对于整数 n ，其可能的完全平方数组合的最大基数不超过 根号n，如果是n会超时。
1. 状态表示：dp[i][j]表示从前i个完全平方数挑选，总和正好等于j，所有的选法中，最小数量。
2. 状态转移方程：当不挑选i^2的时候 dp[i][j] = dp[i - 1][j]
当挑选i的时候分为：挑选一个i^2为 dp[i-1][j - i^2] + 1。
挑选两个i^2为 dp[i-1][j - 2 * i^2] + 2。
挑选两个i^2为 dp[i-1][j - 3 * i^2] + 3....
优化得状态为 dp[i][j-i^2] + 1。
则状态转移方程为：dp[i][j] = Math.min(dp[i-1][j],dp[i][j-i^2] + 1。
3. 初始化 ： 第一列不用初始化，会在填表时候进行填入。而第一行表示从0个数中挑选和为0,1,2,3,4...此时只有dp[0][0]初始化为1，剩下都为0。
4. 填表顺序：
4. 填表顺序：从上向下填填写每一行，但是因为要用到当前元素的左边的元素，所以每一行要从左往右进行填表。
5. 返回值：当dp[m][n]。
class Solution {
public int numSquares(int n) {
// 计算最大可能的平方根
int m = (int)Math.sqrt(n);
// 定义无穷大值，用于初始化
final int INF = 0x3f3f3f3f;
// dp[i][j]表示使用前i个完全平方数组成j所需的最少数量
int[][] dp = new int[m+1][n+1];
// 初始化：使用0个平方数无法组成任何正整数
for(int i = 1; i <= n; i++) dp[0][i] = INF;
// 动态规划填表
for(int i = 1; i <= m; i++){ // 遍历每个平方数
for(int j = 1; j <=n; j++){ // 遍历每个目标数
// 初始值：不使用当前平方数i*i时的解
dp[i][j] = dp[i - 1][j];
// 如果当前目标数j >= i*i，可以考虑使用该平方数
if(j >= i*i){
// 状态转移：取不使用和使用当前平方数的最小值
dp[i][j] = Math.min(dp[i][j], dp[i][j - i*i] + 1);
}
}
}
// 返回使用前m个平方数组成n的最少数量
return dp[m][n];
}
}优化：
class Solution {
public int numSquares(int n) {
// 计算不超过n的最大平方数（物品的最大值）
int m = (int)Math.sqrt(n);
// 定义不可达状态的标记值（比最大可能值大的数）
final int INF = 0x3f3f3f3f;
// dp[j]表示组成整数j所需的最少平方数数量
int[] dp = new int[n+1];
// 初始化：除0外，其他初始状态都设为不可达
for(int i = 1; i <= n; i++) dp[i] = INF;
for(int i = 1; i <= m; i++) { // 遍历每个平方数（物品）
for(int j = i * i; j <= n; j++) { // 完全背包正向遍历
// 状态转移：比较不选当前平方数和选当前平方数的情况
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
}一和零
该题为从字符数组中挑一些字符串，需要满足两个条件，字符串中的零小于等于m，字符串中的1小于等于n。这种满足两个条件的背包问题就称为二维费用的背包问题，而因为每个字符都面临的是选与不选，所以是一个二维费用的01背包问题。
1. 状态表示：dp[i][j][k]，表示从前i个字符串中挑选，满足字符0的个数不超过j，字符1的个数不超过k，所有的选法中，最大的长度。
2. 状态转移方程：和01背包一样分成两种情况
当不选择当前i位置字符串时：dp[i][j][k] = dp[i-1][j][k]。
当选择当前i位置字符串时：dp[i][j][k] = dp[i][j-a][k-b] + 1其中a表示当前字符串0的个数，b表示1的个数，其中j>= a, k>=b
所以dp[i][j][k] = max(dp[i-1][j][k],dp[i][j-a][k-b] + 1)
3. 初始化:无需初始化
4. 填表顺序：保证i从小到大即可
5. 返回值：根据状态表示返回dp[len][m][n]。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// 获取字符串数组的长度
int len = strs.length;
// 创建三维动态规划数组dp[i][j][k]，表示前i个字符串在最多j个0和k个1限制下的最大子集大小
int[][][] dp = new int[len+1][m+1][n+1];
// 遍历每个字符串
for(int i = 1; i <= len; i++){
// a统计当前字符串中'0'的数量，b统计'1'的数量
int a = 0, b = 0;
char[] ch = strs[i-1].toCharArray();
for(int l = 0; l <ch.length; l++){
if(ch[l] == '0') a++;
else b++;
}
// 遍历所有可能的0的数量限制(0到m)
for(int j = 0; j <= m; j++){
// 遍历所有可能的1的数量限制(0到n)
for(int k = 0; k <= n; k++){
// 默认情况：不选当前字符串，继承前i-1个字符串的结果
dp[i][j][k] = dp[i-1][j][k];
// 如果当前0和1的数量限制足够容纳当前字符串
if(j>=a && k>=b){
// 比较不选当前字符串和选当前字符串两种情况，取较大值
dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j-a][k-b]+1);
}
}
}
}
// 返回前len个字符串在最多m个0和n个1限制下的最大子集大小
return dp[len][m][n];
}
}优化：和01背包优化一样去除行，然后更改遍历顺序即可
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// 获取字符串数组的长度
int len = strs.length;
// 创建二维动态规划数组dp[j][k]，表示在最多j个0和k个1限制下的最大子集大小
int[][] dp = new int[m+1][n+1];
// 遍历每个字符串
for(int i = 1; i <= len; i++){
// a统计当前字符串中'0'的数量，b统计'1'的数量
int a = 0, b = 0;
char[] ch = strs[i-1].toCharArray();
for(int l = 0; l <ch.length; l++){
if(ch[l] == '0') a++;
else b++;
}
// 逆向遍历所有可能的0的数量限制(m到a)
// 逆向遍历是为了避免重复计算，保证每次更新时使用的是上一轮(i-1)的结果
for(int j = m; j >= a; j--){
// 逆向遍历所有可能的1的数量限制(n到b)
for(int k = n; k >= b; k--){
// 比较不选当前字符串(dp[j][k])和选当前字符串(dp[j-a][k-b]+1)两种情况
// 取较大值作为新的dp[j][k]的值
dp[j][k] = Math.max(dp[j][k], dp[j-a][k-b]+1);
}
}
}
// 返回在最多m个0和n个1限制下的最大子集大小
return dp[m][n];
}
}盈利计划
该题就是从给的工作数组中挑选一些工作行程一个子集，该子集的要求是工作总人数必须小于等于n，利润必须大于等于m，一共有多少种选择。所以该题和上题是一样的都是二维费用的01背包问题。
1. 状态表示：dp[i][j][k]，表示从前i个计划中挑选，总工作人数不超过j，总利润至少k，一共有多少种选法。
2. 状态转移方程：和01背包一样分成两种情况
当不选择当前i位置字符串时：dp[i][j][k] = dp[i-1][j][k]。
当选择当前i位置字符串时：dp[i][j][k] = dp[i][j-g[i]][k-p[i]] 其中j－g[i]必须大于0，即j大于等于g[i]因为总人数不能超过j，如果j<g[i]总人数就会小于j不满足题目条件, 但是k-p[i]是可以小于0的，因为题目要求的是总利润至少为k也就是当前利润p[i]可以大于总利润k，但是因为代码中数组中是不能小于0的，所以当p[i]大于k时，前面的利润挑选>=0的都可以，所以下标处应该为max(0,k-p[i])
所以dp[i][j][k] = max(dp[i-1][j][k],dp[i][j-a][k-b] + 1)
状态转移方程就有：dp[i][j][k] = dp[i-1][j][k] + dp[i][j-g[i]][k-p[i]]，因为计算出的数可能很大所以进行取模%1e9+7
3. 初始化:当没有任务i = 0时，也就是没有利润，无论人数j是多少，什么都不选利润就(0\，所以dp[0][j][0] = 1。
4. 填表顺序：保证i从小到大即可
5. 返回值：根据状态表示返回最后一个元素即可dp[len][n][m]。len为数组长度，n表示人数限制，m表示利润限制。
class Solution {
public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
// 获取工作数组的长度
int len = group.length;
// 创建三维数组dp，dp[i][j][k]表示从前i个工作中选择，使用不超过j个人，获得至少k利润的方案数
int[][][] dp = new int[len + 1][n + 1][minProfit + 1];
// 初始化：当没有工作时，不管可用人数是多少，获得利润为0的方案数都为1（即什么都不选）
for (int i = 0; i <= n; i++) {
dp[0][i][0] = 1;
}
// 遍历每个工作
for (int i = 1; i <= len; i++) {
// 遍历可用人数
for (int j = 0; j <= n; j++) {
// 遍历所需利润
for (int k = 0; k <= minProfit; k++) {
// 不选择当前工作的方案数，等于从前i - 1个工作中选择的方案数
dp[i][j][k] = dp[i - 1][j][k];
// 如果当前可用人数j大于等于当前工作所需人数group[i - 1]，则可以选择当前工作
if (j >= group[i - 1]) {
// 计算选择当前工作后，剩余需要达到的最小利润
int max = Math.max(0, k - profit[i - 1]);
// 选择当前工作的方案数，累加到总的方案数中
dp[i][j][k] += dp[i - 1][j - group[i - 1]][max];
// 由于结果可能很大，对10^9 + 7取模
dp[i][j][k] %= (1e9 + 7);
}
}
}
}
// 返回最终结果，即从前len个工作中选择，使用不超过n个人，获得至少minProfit利润的方案数
return dp[len][n][minProfit];
}
}优化：
class Solution {
public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
// 获取工作的数量
int len = group.length;
// 创建二维数组 dp，dp[j][k] 表示使用不超过 j 个人，获得至少 k 利润的方案数
int[][] dp = new int[n + 1][minProfit + 1];
// 初始化 dp 数组：当需要的利润为 0 时，不管可用人数是多少，都有一种方案（即什么工作都不选）
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 遍历每一个工作
for (int i = 1; i <= len; i++) {
// 从最大可用人数 n 开始，倒序遍历到当前工作所需的人数 group[i - 1]
// 倒序遍历是为了避免在更新 dp 数组时覆盖掉后续需要用到的旧值，类似于 0 - 1 背包问题的空间优化
for (int j = n; j >= group[i - 1]; j--) {
// 从要求的最小利润 minProfit 开始，倒序遍历到 0
for (int k = minProfit; k >= 0; k--) {
// 计算选择当前工作后，还需要达到的最小利润
// 若当前工作的利润大于等于所需利润 k，则剩余需要达到的利润为 0
int max = Math.max(0, k - profit[i - 1]);
// 状态转移：选择当前工作的方案数累加到总的方案数中
// 即使用 j 个人获得至少 k 利润的方案数等于之前的方案数加上使用 j - group[i - 1] 个人获得至少 max 利润的方案数
dp[j][k] += dp[j - group[i - 1]][max];
dp[j][k] %= 1e9 + 7;
}
}
}
// 返回最终结果，即使用不超过 n 个人，获得至少 minProfit 利润的方案数
return dp[n][minProfit];
}
}组合总数IV
这道题是排列总和问题，其特殊之处在于即使组合中的数字相同，但只要顺序不同，就被认定为不同的情况。背包问题主要用于解决在有限制条件下的“组合”类问题，由于本题重点关注排列顺序，与传统背包问题的侧重点不同，所以不能直接采用背包思想来解决，而是使用普通的动态规划方法就可以有效处理。
1.状态表示:根据分析问题中的过程中，发现重复子问题，抽象出的状态表示，定义dp[i]来表示凑成总和为i时，总共存在多少种排列数。这里的i代表了从0到目标值的各个可能的总和值，而 dp[i]所记录的就是针对该总和值i的所有不同排列组合的数量。
2.状态转移方程:对于 dp[i]的计算，有 dp[i]+= dp[i- nums[j]。这里需要进行一个判断条件即i要大于等于 nums[j]。这是因为只有当当前要凑成的总和i大于或等于数组 nums 中的某个元素nums[j]时，才能够在原来凑成i - nums[j]的排列基础上，通过添加 nums[j]来得到凑成i的新排列。也就是说，对于每一个满足条件的 nums[j]，我们都可以将 dp[i - nums[j]]的值累加到 dp[i]上，从而得到 dp[i]的最终结果。
3.初始化:在动态规划的过程中，因为后续的状态计算会依赖于之前的状态，所以需要对第一个位置进行初始化处理。对于 dp[0]，要凑成总和为0的情况，只需要不选择任何数字即可，这是唯一的一种选择方式，所以 dp[01=1。
4.填表顺序:在填充 dp 数组时，按照从左往右的顺序进行。这是因为每一个 dp[i]的值都是基于前面已经计算好的 dp 值来确定的，从左往右的顺序能够保证在计算 dp[i]时，所依赖的 dp[i - nums[j11的值已经是正确计算出来的。
5.返回值:当整个动态规划过程完成，dp 数组中的值都已经正确计算出来后，只需要返回 dp[target]即可。dp[target]所记录的就是凑成目标值 target 时，所有不同排列的数量。
class Solution {
public int combinationSum4(int[] nums, int target) {
// 创建一个长度为 target + 1 的一维数组 dp
// dp[i] 表示组合成数值 i 的组合数量
int[] dp = new int[target + 1];
// 初始化 dp[0] 为 1，因为组合成数值 0 只有一种方式，即不选择任何元素
dp[0] = 1;
// 遍历从 1 到 target 的每个数值
for (int i = 1; i <= target; i++) {
// 遍历数组 nums 中的每个元素
for (int x : nums) {
// 只有当 当前要组合的数值 i 大于等于数组中的元素 x 时，才进行状态转移
if (i >= x) {
// 状态转移方程：dp[i] 等于之前的组合数量加上 dp[i - x]
// 也就是在组合成 i - x 的所有组合后面加上元素 x，就可以得到组合成 i 的新组合
dp[i] += dp[i - x];
}
}
}
// 返回组合成目标值 target 的组合数量
return dp[target];
}
}不同的二叉搜索树
96. 不同的二叉搜索树 - 力扣（LeetCode）
1.状态表示：定义一个一维数组 dp，其中 dp[i]表示使用i个不同的节点所能构造出的二又搜索树的总数。这里的i取值范围是从0到题目所给定的节点数量n。例如，dp[3]就代表使用3个不同节点时，所有可能构造出的二叉搜索树的种类数量。
2.状态转移方程：对于状态转移方程，需要考虑以每个节点作为根节点时的情况。假设当前要计算使用i个节点构造二叉搜索树的数量，我们依次选取这i个节点中的每一个节点j作为根节点(1 ≤j≤i)。
当以节点j作为根节点时，根据二叉搜索树的性质，其左子树将由1到j-1这j-1个节点构成，而右子树则由j+1到i这i-j个节点构成。由于左子树和右子树的构造是相互独立的，所以以节点j为根节点的二叉搜索树的数量就等于左子树的构造数量乘以右子树的构造数量，即 dp[j- 1]* dp[i - j]。
需要遍历所有可能的根节点 j，并将每种情况下的二叉搜索树数量累加起来，就可以得到使用i个节点构造二叉搜索树的总数量。因此，状态转移方程为 dp[i]+= dp[j-1]* dp[i - j]。
3.初始化：在动态规划的过程中，需要对初始状态进行定义。当节点数量为0时，可以认为存在一种特殊的二叉搜索树，即空树。所以，将 dp[0]初始化为 1，也就是 dp[0]= 1。
4.填表顺序：为了保证在计算 dp[i]时，所依赖的 dp[j-1]和 dp[i-j](其中j-1<i且i-j<i)都已经计算出来，需要按照从左往右的顺序依次填充 dp 数组。也就是先计算 dp[1]，再计算 dp[2]，以此类推，直到计算出 dp[n]。
5.返回值：根据前面定义的状态表示，dp[n]就表示使用n个不同节点所能构造出的二叉搜索树的总数。所以，最终返回 dp[n]作为问题的答案。
class Solution {
public int numTrees(int n) {
// 创建一个长度为 n + 1 的数组 dp
// dp[i] 表示由 i 个不同节点能组成的二叉搜索树的数量
int[] dp = new int[n + 1];
// 初始化 dp[0] 为 1
// 当节点数量为 0 时，可认为存在一种特殊的空树结构
dp[0] = 1;
// 外层循环，从 1 到 n 依次计算不同节点数量下的二叉搜索树数量
for (int i = 1; i <= n; i++) {
// 内层循环，对于 i 个节点的情况，尝试以每个节点 j 作为根节点
for (int j = 1; j <= i; j++) {
// 以节点 j 作为根节点时
// 左子树的节点数量为 j - 1，其能组成的二叉搜索树数量为 dp[j - 1]
// 右子树的节点数量为 i - j，其能组成的二叉搜索树数量为 dp[i - j]
// 根据乘法原理，左右子树的组合情况相乘，得到以 j 为根节点时的二叉搜索树数量
// 再将所有以不同节点为根的情况累加，得到 dp[i]
dp[i] += dp[j - 1] * dp[i - j];
}
}
// 返回由 n 个不同节点能组成的二叉搜索树的数量
return dp[n];
}
}更多推荐
83
0- 0
已为社区贡献1条内容
所有评论(0)