LeetCode.322 零钱兑换
题目链接 零钱兑换
题解
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount == 0) return 0;
int[] dp = new int[amount + 1];
Arrays.fill(dp,Integer.MAX_VALUE-1);
dp[0] = 0;
for(int j = 0;j<=amount;j++){
for(int i = 0;i<coins.length;i++){
if(j < coins[i]) continue;
dp[j] = Math.min(dp[j],dp[j-coins[i]] + 1);
}
}
return dp[amount] == Integer.MAX_VALUE-1 ? -1 : dp[amount];
}
}解题思路
问题是说，给定不同面额的硬币 coins 和一个总金额 amount，要计算凑成总金额所需的最少硬币个数，要是凑不成，就返回 - 1。
算法的思路是这样的：
- 定义 dp 数组，dp [j] 代表凑成金额 j 需要的最少硬币个数。
- 先处理特殊情况，如果 amount 是 0，直接返回 0，因为不需要硬币。
- 初始化 dp 数组，长度是 amount + 1，这样能涵盖从 0 到 amount 的所有金额。把数组里的元素都设为 Integer.MAX_VALUE - 1，这是个很大的数，用来表示暂时还凑不成对应的金额，减 1 是为了后面加 1 的时候不会溢出。然后把 dp [0] 设为 0，因为凑 0 元不需要硬币。
- 接下来填充 dp 数组，外层循环遍历从 0 到 amount 的每个金额 j，内层循环遍历每个硬币面额。
- 对于每个金额 j 和硬币 i，如果硬币面额 coins [i] 大于 j，那这个硬币用不了，就跳过。否则，就看是不用这个硬币时的当前 dp [j] 小，还是用了这个硬币（也就是 dp [j - coins [i]] + 1）小，取其中小的来更新 dp [j]。
- 最后看 dp [amount] 是不是还是一开始设的那个大值，如果是，说明凑不成，返回 - 1，否则就返回 dp [amount]。
LeetCode.279 完全平方数
题目链接 完全平方数
题解
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
for(int j = 0;j<=n;j ++) dp[j] = Integer.MAX_VALUE - 1;
dp[0] = 0;
for(int j = 0;j<=n;j++){
for(int i = 1;i * i <= j;i++){
dp[j] = Math.min(dp[j],dp[j-i*i] + 1);
}
}
return dp[n];
}
}解题思路
问题背景是：给定一个整数 n，找到最少数量的完全平方数（如 1、4、9、16 等），它们的和等于 n。
算法思路解析：
定义 dp 数组，其中 dp [j] 表示 “组成整数 j 所需的最少完全平方数的个数”。
初始化处理：
- 创建长度为 n+1 的 dp 数组（覆盖从 0 到 n 的所有整数）
- 初始时将所有元素设为 Integer.MAX_VALUE - 1（一个极大值，代表 “暂时无法组成”）
- 特别设置 dp [0] = 0（组成 0 需要 0 个完全平方数）
核心计算逻辑：
- 外层循环遍历从 0 到 n 的每个整数 j
- 内层循环遍历所有可能的完全平方数 i²（i 从 1 开始，直到 i² ≤ j）
- 对于每个 j 和有效的 i，更新 dp [j] 为 “不使用 i² 的当前解” 和 “使用 i² 后的解（即 dp [j-i²] + 1）” 中的最小值
最终结果：dp [n] 就是组成整数 n 所需的最少完全平方数的个数
这个算法的时间复杂度为 O (n√n)，因为外层循环是 n 次，内层循环对于每个 j 最多需要√j 次迭代。空间复杂度为 O (n)，用于存储 dp 数组。
LeetCode.139 单词拆分
题目链接 单词拆分
题解
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> set = new HashSet<>(wordDict);
boolean[] valid = new boolean[s.length() + 1];
valid[0] = true;
for(int i = 1;i<=s.length();i++){
for(int j = 0;j<i && !valid[i];j++){
if (set.contains(s.substring(j, i)) && valid[j]) {
valid[i] = true;
}
}
}
return valid[s.length()];
}
}解题思路
问题背景是：给定一个非空字符串s和一个包含非空单词的列表wordDict，判断字符串s是否可以被拆分为若干个在词典中出现的单词拼接而成。
算法思路解析：
数据准备：
- 将
wordDict转换为HashSet，便于快速判断某个是否在词典中存在 - 创建一个
valid布尔数组，其中valid[i]表示 “字符串s的前i个字符组成的子串是否可以被拆分成词典中的单词”
- 将
初始化处理：
valid[0] = true：表示空字符串可以被成功拆分（作为后续判断提供基础）- 数组长度为
s.length() + 1，覆盖从 0 到字符串长度的所有位置
核心计算逻辑：
- 外层循环
i从 1 遍历到s.length()，表示判断前i个字符组成的子串是否可拆分 - 内层循环
j从 0 遍历到i-1，尝试将前i个字符拆分为前j个字符和j到i之间的子串 - 若前
j个字符可拆分（valid[j]为true），且j到i之间的子串在词典中存在，则标记valid[i]为true - 一旦
valid[i]被标记为true，就可以提前内层当前内层循环（通过!valid[i]条件控制）
- 外层循环
最终结果：
valid[s.length()]的值即为字符串s是否可以被拆分的答案
这个算法的时间复杂度为 O (n²)，其中 n 是字符串s的长度；空间复杂度为 O (n)，主要用于存储valid数组和HashSet。
卡码网.56 多重背包
题目链接 多重背包
题解
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int c = sc.nextInt();
int n = sc.nextInt();
int[] weight = new int[n];
int[] value = new int[n];
int[] nums = new int[n];
for(int i = 0;i<n;i++) weight[i] = sc.nextInt();
for(int i = 0;i<n;i++) value[i] = sc.nextInt();
for(int i = 0;i<n;i++) nums[i] = sc.nextInt();
int[] dp = new int[c+1];
for(int i = 0;i<n;i++){
for(int j = c;j>=weight[i];j--){
for(int k = 1;k<=nums[i] && (j - k * weight[i]) >= 0;k++){
dp[j] = Math.max(dp[j],dp[j-k*weight[i]] + k*value[i]);
}
}
}
System.out.println(dp[c]);
}
}解题思路
问题背景是：给定一个背包容量c，以及n种物品，每种物品有重量weight[i]、价值value[i]和数量nums[i]的限制。要求在不超过背包容量的前提下，选择物品放入背包，使得总价值最大。
程序思路解析：
输入处理：
- 通过
Scanner读取背包容量c和物品数量n - 分别读取每种物品的重量、价值和数量，存储在对应数组中
- 通过
动态规划数组定义：
- 创建
dp数组，dp[j]表示 " 背包容量为j时能获得的最大价值 " - 数组长度为
c+1，覆盖从 0 到c的所有容量
- 创建
核心计算逻辑（三重循环）：
- 外层循环遍历每种物品（
i从 0 到 n-1） - 中层循环从背包最大容量
c向前遍历到当前物品重量（0-1 背包的标准遍历方式，避免重复使用） - 内层循环尝试当前物品的不同数量（
k从 1 到最大数量nums[i]，且不超过当前背包剩余容量） - 状态转移：
dp[j]取 "不放入 k 个当前物品的价值" 和 " 放入 k 个当前物品的价值（即dp[j-k*weight[i]] + k*value[i]）" 中的最大值
- 外层循环遍历每种物品（
输出结果：
dp[c]即为背包容量为c时能获得的最大价值
这个算法的时间复杂度较高，为 O (n×c×k)，其中 n 是物品数量，c 是背包容量，k 是物品的平均数量。空间复杂度为 O (c)，用于存储 dp 数组。