当前位置：首页 > news >正文

代码随想录算法训练营第三十八天

news 2025/8/2 7:44:37

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时能获得的最大价值