代码随想录算法训练营第三十七天
卡码网.52 携带研究材料
题目链接 携带研究材料
题解
import java.util.Scanner;
public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int v = sc.nextInt();int[] weight = new int[n + 1];int[] value = new int[n+1];for(int i = 0;i<n;i++){weight[i] = sc.nextInt();value[i] = sc.nextInt();}int[] dp = new int[v + 1];for(int i = 0;i<n;i++){for(int j = weight[i];j<=v;j++){dp[j] = Math.max(dp[j],dp[j-weight[i]] + value[i]);}}System.out.println(dp[v]);}
}解题思路
这道题目是经典的「0-1 背包问题」，解题思路基于动态规划。假设有 n 件物品，每件有重量 weight [i] 和价值 value [i]，背包容量为 v，每件物品只能选一次，目标是在不超过容量的前提下让总价值最大。首先定义 dp 数组，其中 dp [j] 表示容量为 j 的背包能装的最大价值。状态转移方程是核心：对于每件物品，判断是否放入背包，不放入则 dp [j] 不变，放入则等于容量 j - weight [i] 时的最大价值加当前物品价值，即 dp [j] = max (dp [j], dp [j - weight [i]] + value [i])。遍历顺序很关键，外层循环遍历每件物品，内层循环从背包最大容量 v 逆序遍历到当前物品重量，这样能保证每件物品只被选一次。初始化时 dp [0] 为 0，其他为 0，因为初始状态背包无物品。最后 dp [v] 就是容量为 v 的背包能装的最大价值。比如 n=2，v=3，物品 1 重量 2 价值 5，物品 2 重量 1 价值 3，处理物品 1 后 dp 变为 [0,0,5,5]，处理物品 2 后最终 dp [3] 为 5，即选物品 1 是最优解。这种方法时间复杂度 O (n*v)，用一维数组优化了空间，逆序遍历是区分 0-1 背包和完全背包的关键。
LeetCode.518 零钱兑换II
题目链接 零钱兑换II
题解
class Solution {public int change(int amount, int[] coins) {// dp数组最多有dp[j]种方法得到总金额jint[] 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] + dp[j - coins[i]];}}return dp[amount];}
}解题思路
这段代码解决的是「零钱兑换 II」问题，即计算用给定的硬币组合出目标金额的不同方式数量（硬币可以重复使用，且组合顺序不影响结果）。核心思路基于动态规划：
定义 dp [j] 表示组合出金额 j 的方法数，初始化 dp [0] = 1（只有 1 种方式组合出金额 0，即不使用任何硬币）。
外层循环遍历每种硬币，内层循环从当前硬币面额开始遍历到目标金额，状态转移方程为 dp [j] += dp [j - coins [i]]，表示在已有的组合方式基础上，加上使用当前硬币后新增的组合方式（即凑出金额 j - coins [i] 的方法数）。
这种遍历顺序（先遍历硬币，再正序遍历金额）确保了每种硬币可以被重复使用，且不会计算顺序不同的相同组合（如 1+2 和 2+1 被视为同一种组合）。最终 dp [amount] 就是组合出目标金额的总方法数。
LeetCode.377 组合总和 Ⅳ
题目链接 组合总和 Ⅳ
题解
class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;for(int j = 0;j <=target;j++){for(int i = 0;i < nums.length;i++){if(j < nums[i]) continue;dp[j] += dp[j-nums[i]];}}return dp[target];}
}解题思路
这段代码解决的是「组合总和 IV」问题，计算使用给定数组中的元素（可重复使用）组合出目标值的不同排列方式数量（顺序不同视为不同组合）。核心思路是动态规划：
定义 dp [j] 表示组合出目标值 j 的排列方式数，初始化 dp [0] = 1（只有 1 种方式得到 0，即不选任何元素）。
外层循环遍历目标值从 0 到 target，内层循环遍历数组中的每个元素，当元素值小于等于当前目标值 j 时，状态转移方程为 dp [j] += dp [j - nums [i]]，表示在组合出 j - nums [i] 的基础上加上当前元素 nums [i] 形成新的排列。
这种遍历顺序（先遍历目标值，再遍历数组元素）确保了不同顺序的组合被视为不同情况（如 1+2 和 2+1 会被分别计数）。最终 dp [target] 就是组合出目标值的所有排列方式总数。
卡码网.57 爬楼梯
题目链接 爬楼梯
题解
import java.util.Scanner;
public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] dp = new int[n + 1];dp[0] = 1;for(int j = 0;j<=n;j++){for(int i = 1;i<=m;i++){if(j >= i)dp[j] += dp[j-i];}}System.out.println(dp[n]);}
}解题思路
这段代码解决的是一个组合计数问题，可以理解为 "用 1 到 m 的数字（可重复使用）相加得到 n 的不同组合方式有多少种，其中顺序不同算作不同组合"。
代码核心思路基于动态规划：定义 dp [j] 表示得到数字 j 的组合方式数，初始化 dp [0] = 1（只有 1 种方式得到 0，即不选任何数字）。外层循环遍历目标值从 0 到 n，内层循环遍历 1 到 m 的数字，当数字 i 小于等于当前目标值 j 时，状态转移方程为 dp [j] += dp [j - i]，表示在得到 j - i 的基础上加上 i 形成新的组合。这种遍历顺序确保了不同顺序的组合被分别计数（如 1+2 和 2+1 会被算作两种不同方式）。最终 dp [n] 就是得到数字 n 的所有组合方式总数。