以下是 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 代码typescriptfunction 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。
)
