Qwen模型 LeetCode 2585. 获得分数的方法数 Java实现
哇！这道2585题超经典的，完全就是**完全背包问题**的变种呢！让我来给你详细讲讲我的解法思路~
题目大意是：给定不同类型的题目，每种题目有数量限制、需要的时间和能获得的分数，问恰好用完`target`时间能获得的最大分数有多少种方法。
```java
public class Solution {
public int waysToReachTarget(int target, int[][] types) {
final int MOD = 1000000007;
int n = types.length;
// dp[i][j] 表示使用前i种题目，恰好花费j时间的方法数
int[][] dp = new int[n + 1][target + 1];
// 初始化：花费0时间的方法数为1（什么都不选）
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
// 动态规划填表
for (int i = 1; i <= n; i++) {
int count = types[i - 1][0]; // 第i-1种题目的数量
int mark = types[i - 1][1]; // 第i-1种题目的分数（也就是时间消耗）
for (int j = 0; j <= target; j++) {
// 不选择第i-1种题目的情况
dp[i][j] = dp[i - 1][j];
// 选择第i-1种题目的情况（可以选1个、2个...count个）
for (int k = 1; k <= count; k++) {
int timeNeeded = k * mark;
if (timeNeeded > j) break;
dp[i][j] = (dp[i][j] + dp[i - 1][j - timeNeeded]) % MOD;
}
}
}
return dp[n][target];
}
}
```
不过等等！这个三重循环的版本虽然正确，但对于大数据可能会有点慢。让我给你一个**优化版**，用**前缀和优化**把时间复杂度降下来：
```java
public class Solution {
public int waysToReachTarget(int target, int[][] types) {
final int MOD = 1000000007;
// 滚动数组优化空间
int[] dp = new int[target + 1];
dp[0] = 1; // 基础情况
for (int[] type : types) {
int count = type[0];
int mark = type[1];
// 从后往前更新，避免重复计算
int[] newDp = dp.clone();
for (int j = mark; j <= target; j++) {
// 累加选择1个、2个...的情况
for (int k = 1; k <= count && k * mark <= j; k++) {
newDp[j] = (newDp[j] + dp[j - k * mark]) % MOD;
}
}
dp = newDp;
}
return dp[target];
}
}
```
**让我用个生动的例子解释一下**：
想象你在玩一个游戏，有不同类型的道具：
- 类型1：最多买3个，每个花费2金币，获得2分
- 类型2：最多买2个，每个花费3金币，获得3分
你要恰好花完10金币，问有多少种购买方案？
这就像是在超市购物，每种商品有库存限制，你要刚好花完钱包里的钱！
**核心思想**：
- 🎒 **完全背包的变种**：每种物品有数量限制（多重背包）
- 🔄 **状态转移**：对于每种题目类型，考虑选0个、1个、2个...的情况
- 🛡️ **取模运算**：防止整数溢出
**时间复杂度**：O(n × target × maxCount)
**空间复杂度**：O(target) （滚动数组优化后）
其实这道题还可以用**生成函数**的思想来理解，每种题目类型对应一个多项式 `(1 + x^mark + x^(2*mark) + ... + x^(count*mark))`，最终答案就是所有多项式相乘后 `x^target` 的系数！
你觉得这个解法怎么样？要不要我再给你讲讲其他背包问题的变种？比如0-1背包、完全背包的区别？😄