2026-06-08恰好 K 个下标对的最大得分。用go语言给定两个整数数组 nums1长度 n和 nums2长度 m以及一个整数 k。你需要从两个数组中各选出 k 个下标对满足下标对的顺序严格递增选中的下标对为 (i1, j1), (i2, j2), …, (ik, jk)必须满足0 ≤ i1 i2 … ik n并且 0 ≤ j1 j2 … jk m每选中一个下标对 (i, j)就能得到分数 nums1[i] × nums2[j]总分等于所有 k 个选择对应分数的加和任务求在满足上述条件的前提下能够得到的最大总分是多少。1 n nums1.length 100。1 m nums2.length 100。-1000000 nums1[i], nums2[i] 1000000。1 k min(n, m)。输入 nums1 [1,3,2], nums2 [4,5,1], k 2。输出 22。解释一种最优的下标对选择方案是(i1, j1) (1, 0)得分为 3 * 4 12(i2, j2) (2, 1)得分为 2 * 5 10总得分为 12 10 22。题目来自力扣3836。一、分步骤详细执行过程整个过程分为K轮循环因为要选恰好K个下标对每一轮对应「选第t个下标对」t从1到K。步骤1初始化准备创建两个大小为(n1) × (m1)的二维数组 f、gn是nums1长度m是nums2长度。所有位置填充极小值代表初始状态不可达。第一轮循环开始目标计算选1个下标对的最大得分。步骤2第1轮循环选第1个下标对t1这一轮要找到所有满足i₁ nj₁ m的单个下标对计算得分保留最大值。边界预处理先把不合法的位置无法选1个下标对的位置标记为极小值排除无效状态。遍历所有合法的(i,j)遍历nums1的每个位置i、nums2的每个位置j满足选1个下标对下标无递增约束只要在数组内状态更新g[i1][j1]取三种情况的最大值✅ 不选当前i继承上方状态g[i][j1]✅ 不选当前j继承左方状态g[i1][j]✅ 选当前(i,j)作为第1个下标对nums1[i] * nums2[j]数组交换计算完成后f和g交换此时f数组存储了「选1个下标对」的所有最大得分。对应示例选1个的最大得分是 3×515i1,j1。步骤3第2轮循环选第2个下标对t2直到K轮这是关键轮次必须满足下标严格递增i₂i₁j₂j₁。边界预处理因为要选2个下标对必须预留足够的后续元素所以把无法选2个的位置标记为极小值。遍历所有合法的(i,j)遍历nums1和nums2的位置严格满足当前i 上一个选中的i₁当前j 上一个选中的j₁状态更新规则g[i1][j1] 最大值不选i、不选j、选当前(i,j)选当前(i,j)时得分 上一轮f[i][j]选1个的最大得分 nums1[i]×nums2[j]数组交换交换后f数组存储选2个下标对的最大得分。对应示例上一轮选1个的最优是15本轮找到组合选(1,0)得12 → 再选(2,1)得10 → 总分22这就是全局最大值。步骤4循环结束获取结果完成K轮循环后f[n][m]就是在nums1全部n个元素、nums2全部m个元素中恰好选K个合法下标对的最大总分。最后将结果转为int64返回。二、时间复杂度分析时间复杂度由三层循环决定最外层循环K次选K个下标对中间层遍历nums1的所有元素次数为n最内层遍历nums2的所有元素次数为m总时间复杂度O(K × n × m)题目约束n、m≤100K≤100计算量100×100×1001e6完全满足运行要求。三、额外空间复杂度分析额外空间仅用于两个动态规划二维数组f数组(n1) × (m1)g数组(n1) × (m1)总额外空间复杂度O(n × m)没有使用其他递归栈、集合等额外空间空间效率很高。总结解题核心滚动二维动态规划用两个数组交替记录选t个下标对的最大得分执行过程分K轮循环每轮计算选t个的最优解严格保证下标递增时间复杂度O(K·n·m)三层循环驱动额外空间复杂度O(n·m)仅使用两个二维状态数组。Go完整代码如下packagemainimport(fmtmath)funcmaxScore(nums1,nums2[]int,Kint)int64{n,m:len(nums1),len(nums2)f:make([][]int,n1)g:make([][]int,n1)fori:rangef{f[i]make([]int,m1)g[i]make([]int,m1)}fork:1;kK;k{forj:k;jm-(K-k);j{g[k-1][j]math.MinInt}fori:k-1;in-(K-k);i{// 后面还要选 K-k 个下标对g[i1][k-1]math.MinIntforj:k-1;jm-(K-k);j{g[i1][j1]max(g[i][j1],g[i1][j],f[i][j]nums1[i]*nums2[j])}}f,gg,f}returnint64(f[n][m])}funcmain(){nums1:[]int{1,3,2}nums2:[]int{4,5,1}k:2result:maxScore(nums1,nums2,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importmathdefmaxScore(nums1,nums2,K):n,mlen(nums1),len(nums2)# 初始化两个DP表用于滚动数组优化f[[0]*(m1)for_inrange(n1)]g[[0]*(m1)for_inrange(n1)]# 外循环从1到K表示已选择的对数forkinrange(1,K1):# 初始化g表的边界条件forjinrange(k,m-(K-k)1):g[k-1][j]-math.infforiinrange(k-1,n-(K-k)):g[i1][k-1]-math.infforjinrange(k-1,m-(K-k)):g[i1][j1]max(g[i][j1],g[i1][j],f[i][j]nums1[i]*nums2[j])# 交换f和g实现滚动数组f,gg,freturnf[n][m]defmain():nums1[1,3,2]nums2[4,5,1]k2resultmaxScore(nums1,nums2,k)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includealgorithm#includeclimitsusingnamespacestd;longlongmaxScore(vectorintnums1,vectorintnums2,intK){intnnums1.size();intmnums2.size();// 初始化两个DP表用于滚动数组优化vectorvectorintf(n1,vectorint(m1));vectorvectorintg(n1,vectorint(m1));// 外循环从1到K表示已选择的对数for(intk1;kK;k){// 初始化g表的边界条件for(intjk;jm-(K-k);j){g[k-1][j]INT_MIN;}for(intik-1;in-(K-k);i){g[i1][k-1]INT_MIN;for(intjk-1;jm-(K-k);j){g[i1][j1]max({g[i][j1],g[i1][j],f[i][j]nums1[i]*nums2[j]});}}// 交换f和g实现滚动数组swap(f,g);}return(longlong)f[n][m];}intmain(){vectorintnums1{1,3,2};vectorintnums2{4,5,1};intk2;longlongresultmaxScore(nums1,nums2,k);coutresultendl;return0;}