Kimi LeetCode 3836. 恰好 K 个下标对的最大得分 TypeScript实现

以下是 LeetCode 3836. 恰好 K 个下标对的最大得分 的 TypeScript 实现。

解题思路

三维动态规划。定义 `dp[i][j][k]` 为：在 `nums1` 的前 `i` 个元素和 `nums2` 的前 `j` 个元素中，恰好选择 `k` 对下标所能获得的最大得分。

状态转移有三种情况：
1. 跳过 `nums1[i-1]`：`dp[i][j][k] = dp[i-1][j][k]`
2. 跳过 `nums2[j-1]`：`dp[i][j][k] = dp[i][j-1][k]`
3. 将 `nums1[i-1]` 与 `nums2[j-1]` 配对：`dp[i][j][k] = dp[i-1][j-1][k-1] + nums1[i-1] * nums2[j-1]`

取三者最大值。初始状态 `dp[0][0][0] = 0`，其余为负无穷。

---

TypeScript 代码

```typescript
function maxScore(nums1: number[], nums2: number[], k: number): number {
const n = nums1.length;
const m = nums2.length;
const K = k;
const NEG = -1e18; // 足够小的负无穷

// dp[i][j][k]: 前i个nums1和前j个nums2中选k对的最大得分
const dp: number[][][] = Array.from({ length: n + 1 }, () =>
Array.from({ length: m + 1 }, () => Array(K + 1).fill(NEG))
);
dp[0][0][0] = 0;

for (let i = 0; i <= n; i++) {
for (let j = 0; j <= m; j++) {
for (let kk = 0; kk <= K; kk++) {
// 不选 nums1[i-1]
if (i > 0) {
dp[i][j][kk] = Math.max(dp[i][j][kk], dp[i - 1][j][kk]);
}
// 不选 nums2[j-1]
if (j > 0) {
dp[i][j][kk] = Math.max(dp[i][j][kk], dp[i][j - 1][kk]);
}
// 将 nums1[i-1] 和 nums2[j-1] 配对
if (i > 0 && j > 0 && kk > 0) {
dp[i][j][kk] = Math.max(
dp[i][j][kk],
dp[i - 1][j - 1][kk - 1] + nums1[i - 1] * nums2[j - 1]
);
}
}
}
}

return dp[n][m][K];
}
```

---

关键注意点

要点 说明
返回值类型 TypeScript/JavaScript 的 `number` 为双精度浮点数，最大安全整数约为 `9 × 10^15`。本题最大得分约为 `100 × 10^6 × 10^6 = 10^14`，完全在安全整数范围内，无需额外处理。
负无穷取值 使用 `-1e18` 作为负无穷标记，既足够小又不会引发浮点精度问题。
三维数组初始化 使用 `Array.from` 嵌套创建三维数组，确保每一层都是独立的引用，避免共享数组导致的数据污染。
时间复杂度 `O(n × m × K)`，约 `10^6` 次运算，轻松通过。
空间复杂度 `O(n × m × K)`，约 `10^6` 个数字，内存占用约 830 MB。