Qwen模型 LeetCode 2585. 获得分数的方法数 TypeScript实现
哇！TypeScript版本来啦～这道题用TS写起来特别优雅，类型安全又清晰！让我给你展示一个高效又易读的实现！
```typescript
function waysToReachTarget(target: number, types: number[][]): number {
const MOD = 1000000007;
// dp[j] 表示恰好花费j时间的方法数
const dp: number[] = new Array(target + 1).fill(0);
dp[0] = 1; // 基础情况：花费0时间有1种方法（什么都不选）
// 遍历每种题目类型
for (const [count, mark] of types) {
// 创建新的dp数组，避免在更新过程中使用已修改的值
const newDp: number[] = [...dp];
// 对于每个可能的时间花费
for (let time = mark; time <= target; time++) {
// 尝试选择1个、2个...count个当前类型的题目
for (let k = 1; k <= count; k++) {
const neededTime = k * mark;
if (neededTime > time) break;
newDp[time] = (newDp[time] + dp[time - neededTime]) % MOD;
}
}
// 更新dp数组
dp.splice(0, dp.length, ...newDp);
}
return dp[target];
}
```
不过等等！这个版本虽然清晰，但还可以进一步**优化性能**。让我给你一个更高效的版本，避免数组复制的开销：
```typescript
function waysToReachTarget(target: number, types: number[][]): number {
const MOD = 1000000007;
// 使用滚动数组，从后往前更新
const dp: number[] = new Array(target + 1).fill(0);
dp[0] = 1;
for (const [count, mark] of types) {
// 从target到mark倒序遍历，避免重复计算
for (let time = target; time >= mark; time--) {
// 临时变量记录新增的方法数
let add = 0;
// 计算选择1到count个当前类型题目的贡献
for (let k = 1; k <= count && k * mark <= time; k++) {
add = (add + dp[time - k * mark]) % MOD;
}
dp[time] = (dp[time] + add) % MOD;
}
}
return dp[target];
}
```
**✨ TypeScript的优势体现**：
1. **类型安全**：`target: number`, `types: number[][]` 让代码意图一目了然
2. **解构赋值**：`for (const [count, mark] of types)` 超简洁！
3. **数组操作**：`new Array(target + 1).fill(0)` 初始化超方便
**让我用个生动的例子解释算法**：
想象你在经营一家魔法商店 🧙♂️：
- **商品类型1**：最多卖3个魔法卷轴，每个售价2金币
- **商品类型2**：最多卖2个魔法药水，每个售价3金币
- **目标**：刚好收10金币，问有多少种销售组合？
这就是典型的**多重背包问题**！每种商品有库存限制，我们要恰好花完（收完）指定金额。
**核心思路**：
- 🎯 **状态定义**：`dp[time]` = 恰好花费`time`时间的方法数
- 🔄 **状态转移**：对每种题目类型，考虑选择0到count个的所有可能性
- 🛡️ **边界处理**：`dp[0] = 1` 是关键的base case
**时间复杂度**：O(n × target × maxCount)
**空间复杂度**：O(target)
其实这个问题还可以用**生成函数**的角度理解：每种题目类型对应多项式 `(1 + x^mark + x^(2*mark) + ... + x^(count*mark))`，答案就是所有多项式乘积中 `x^target` 的系数！
你觉得这个TS实现怎么样？要不要我再给你讲讲其他动态规划的经典套路？比如如何识别背包问题的变种？😄