2026-06-08：恰好 K 个下标对的最大得分。用go语言，给定两个整数数组 nums1（长度 n）和 nums2（长度 m），以及一个整数 k。你需要从两个数组中各选出 k 个下标对，满足下标对
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：初始化准备
- 创建两个大小为
(n+1) × (m+1)的二维数组 f、g（n是nums1长度，m是nums2长度）。 - 所有位置填充极小值（代表初始状态不可达）。
- 第一轮循环开始，目标：计算选1个下标对的最大得分。
步骤2：第1轮循环（选第1个下标对，t=1）
这一轮要找到所有满足i₁ < n，j₁ < m的单个下标对，计算得分，保留最大值。
- 边界预处理
先把不合法的位置（无法选1个下标对的位置）标记为极小值，排除无效状态。 - 遍历所有合法的(i,j)
遍历nums1的每个位置i、nums2的每个位置j，满足：- 选1个下标对，下标无递增约束（只要在数组内）
- 状态更新：
g[i+1][j+1]取三种情况的最大值：
✅ 不选当前i：继承上方状态g[i][j+1]
✅ 不选当前j：继承左方状态g[i+1][j]
✅ 选当前(i,j)作为第1个下标对：nums1[i] * nums2[j]
- 数组交换
计算完成后，f和g交换，此时f数组存储了「选1个下标对」的所有最大得分。
对应示例：
选1个的最大得分是 3×5=15（i=1,j=1）。
步骤3：第2轮循环（选第2个下标对，t=2，直到K轮）
这是关键轮次，必须满足下标严格递增：i₂>i₁，j₂>j₁。
- 边界预处理
因为要选2个下标对，必须预留足够的后续元素，所以把无法选2个的位置标记为极小值。 - 遍历所有合法的(i,j)
遍历nums1和nums2的位置，严格满足：- 当前i > 上一个选中的i₁
- 当前j > 上一个选中的j₁
状态更新规则：g[i+1][j+1]= 最大值（不选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≤100，K≤100，计算量=100×100×100=1e6，完全满足运行要求。
三、额外空间复杂度分析
额外空间仅用于两个动态规划二维数组：
- f数组：(n+1) × (m+1)
- g数组：(n+1) × (m+1)
总额外空间复杂度：O(n × m)
- 没有使用其他递归栈、集合等额外空间，空间效率很高。
总结
- 解题核心：滚动二维动态规划，用两个数组交替记录选t个下标对的最大得分；
- 执行过程：分K轮循环，每轮计算选t个的最优解，严格保证下标递增；
- 时间复杂度：O(K·n·m)，三层循环驱动；
- 额外空间复杂度：O(n·m)，仅使用两个二维状态数组。
Go完整代码如下：
packagemainimport("fmt""math")funcmaxScore(nums1,nums2[]int,Kint)int64{n,m:=len(nums1),len(nums2)f:=make([][]int,n+1)g:=make([][]int,n+1)fori:=rangef{f[i]=make([]int,m+1)g[i]=make([]int,m+1)}fork:=1;k<=K;k++{forj:=k;j<=m-(K-k);j++{g[k-1][j]=math.MinInt}fori:=k-1;i<n-(K-k);i++{// 后面还要选 K-k 个下标对g[i+1][k-1]=math.MinIntforj:=k-1;j<m-(K-k);j++{g[i+1][j+1]=max(g[i][j+1],g[i+1][j],f[i][j]+nums1[i]*nums2[j])}}f,g=g,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,m=len(nums1),len(nums2)# 初始化两个DP表，用于滚动数组优化f=[[0]*(m+1)for_inrange(n+1)]g=[[0]*(m+1)for_inrange(n+1)]# 外循环：从1到K，表示已选择的对数forkinrange(1,K+1):# 初始化g表的边界条件forjinrange(k,m-(K-k)+1):g[k-1][j]=-math.infforiinrange(k-1,n-(K-k)):g[i+1][k-1]=-math.infforjinrange(k-1,m-(K-k)):g[i+1][j+1]=max(g[i][j+1],g[i+1][j],f[i][j]+nums1[i]*nums2[j])# 交换f和g，实现滚动数组f,g=g,freturnf[n][m]defmain():nums1=[1,3,2]nums2=[4,5,1]k=2result=maxScore(nums1,nums2,k)print(result)if__name__=="__main__":main()C++完整代码如下：
#include<iostream>#include<vector>#include<algorithm>#include<climits>usingnamespacestd;longlongmaxScore(vector<int>&nums1,vector<int>&nums2,intK){intn=nums1.size();intm=nums2.size();// 初始化两个DP表，用于滚动数组优化vector<vector<int>>f(n+1,vector<int>(m+1));vector<vector<int>>g(n+1,vector<int>(m+1));// 外循环：从1到K，表示已选择的对数for(intk=1;k<=K;k++){// 初始化g表的边界条件for(intj=k;j<=m-(K-k);j++){g[k-1][j]=INT_MIN;}for(inti=k-1;i<n-(K-k);i++){g[i+1][k-1]=INT_MIN;for(intj=k-1;j<m-(K-k);j++){g[i+1][j+1]=max({g[i][j+1],g[i+1][j],f[i][j]+nums1[i]*nums2[j]});}}// 交换f和g，实现滚动数组swap(f,g);}return(longlong)f[n][m];}intmain(){vector<int>nums1={1,3,2};vector<int>nums2={4,5,1};intk=2;longlongresult=maxScore(nums1,nums2,k);cout<<result<<endl;return0;}