Hard

题目描述

给你两个长度分别为 n 和 m 的整数数组 nums1 和 nums2，以及一个整数 k。

你必须选择恰好 k 对索引 (i1, j1), (i2, j2), ..., (ik, jk)，满足：

  • 0 <= i1 < i2 < ... < ik < n
  • 0 <= j1 < j2 < ... < jk < m

对于每个选择的索引对 (i, j)，你可以获得分数 nums1[i] * nums2[j]。

总分数是所有选中索引对的乘积之和。

返回能够达到的最大总分数。

示例 1：

输入：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。

示例 2：

输入：nums1 = [-2,0,5], nums2 = [-3,4,-1,2], k = 2
输出：26
解释：
一个最优的索引对选择是：
- (i1, j1) = (0, 0)，分数为 -2 * -3 = 6
- (i2, j2) = (2, 1)，分数为 5 * 4 = 20
总分数为 6 + 20 = 26。

示例 3：

输入：nums1 = [-3,-2], nums2 = [1,2], k = 2
输出：-7
解释：
最优的索引对选择是：
- (i1, j1) = (0, 0)，分数为 -3 * 1 = -3
- (i2, j2) = (1, 1)，分数为 -2 * 2 = -4
总分数为 -3 + (-4) = -7。

提示：

  • 1 <= n == nums1.length <= 100
  • 1 <= m == nums2.length <= 100
  • -10^6 <= nums1[i], nums2[i] <= 10^6
  • 1 <= k <= min(n, m)

解题思路

这是一个经典的三维动态规划问题。我们需要在两个数组中选择恰好 k 对索引，使得乘积之和最大。

核心思路：

定义状态 dp[i][j][t] 表示从 nums1[0..i-1] 和 nums2[0..j-1] 中选择恰好 t 对索引能获得的最大分数。

状态转移：

对于每个位置 (i,j)，我们有三种选择：

  1. 不选择 nums1[i-1]：dp[i-1][j][t]
  2. 不选择 nums2[j-1]：dp[i][j-1][t]
  3. 选择当前索引对 (i-1,j-1)：dp[i-1][j-1][t-1] + nums1[i-1] * nums2[j-1]

转移方程为：dp[i][j][t] = max(选择1, 选择2, 选择3)

边界条件：

  • dp[i][j][0] = 0（选择0对，分数为0）
  • 当 t > min(i,j) 时，无法选择 t 对，设为负无穷

优化技巧：

由于数组长度较小（≤100），可以使用记忆化搜索来实现，这样代码更简洁且只计算需要的状态。

代码实现

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<vector<long long>>> memo(n + 1, vector<vector<long long>>(m + 1, vector<long long>(k + 1, LLONG_MIN)));
        
        function<long long(int, int, int)> dfs = [&](int i, int j, int t) -> long long {
            if (t == 0) return 0;
            if (i == 0 || j == 0) return LLONG_MIN / 2;
            if (memo[i][j][t] != LLONG_MIN) return memo[i][j][t];
            
            long long res = LLONG_MIN / 2;
            res = max(res, dfs(i - 1, j, t));
            res = max(res, dfs(i, j - 1, t));
            long long pick = dfs(i - 1, j - 1, t - 1);
            if (pick != LLONG_MIN / 2) {
                res = max(res, pick + (long long)nums1[i - 1] * nums2[j - 1]);
            }
            
            return memo[i][j][t] = res;
        };
        
        return dfs(n, m, k);
    }
};

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        n, m = len(nums1), len(nums2)
        memo = {}
        
        def dfs(i, j, t):
            if t == 0:
                return 0
            if i == 0 or j == 0:
                return float('-inf')
            if (i, j, t) in memo:
                return memo[(i, j, t)]
            
            res = float('-inf')
            res = max(res, dfs(i - 1, j, t))
            res = max(res, dfs(i, j - 1, t))
            pick = dfs(i - 1, j - 1, t - 1)
            if pick != float('-inf'):
                res = max(res, pick + nums1[i - 1] * nums2[j - 1])
            
            memo[(i, j, t)] = res
            return res
        
        return dfs(n, m, k)

public class Solution {
    public long MaxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.Length, m = nums2.Length;
        long[,,] memo = new long[n + 1, m + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int t = 0; t <= k; t++) {
                    memo[i, j, t] = long.MinValue;
                }
            }
        }
        
        long Dfs(int i, int j, int t) {
            if (t == 0) return 0;
            if (i == 0 || j == 0) return long.MinValue / 2;
            if (memo[i, j, t] != long.MinValue) return memo[i, j, t];
            
            long res = long.MinValue / 2;
            res = Math.Max(res, Dfs(i - 1, j, t));
            res = Math.Max(res, Dfs(i, j - 1, t));
            long pick = Dfs(i - 1, j - 1, t - 1);
            if (pick != long.MinValue / 2) {
                res = Math.Max(res, pick + (long)nums1[i - 1] * nums2[j - 1]);
            }
            
            return memo[i, j, t] = res;
        }
        
        return Dfs(n, m, k);
    }
}

var maxScore = function(nums1, nums2, k) {
    const n = nums1.length;
    const m = nums2.length;
    
    // dp[i][j][pairs] = max score using first i elements from nums1, first j elements from nums2, with exactly 'pairs' pairs
    const dp = Array(n + 1).fill(null).map(() => 
        Array(m + 1).fill(null).map(() => 
            Array(k + 1).fill(-Infinity)
        )
    );
    
    // Base case: 0 pairs selected
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= m; j++) {
            dp[i][j][0] = 0;
        }
    }
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            for (let pairs = 0; pairs <= Math.min(i, Math.min(j, k)); pairs++) {
                // Don't take current pair
                dp[i][j][pairs] = Math.max(dp[i-1][j][pairs], dp[i][j-1][pairs]);
                
                // Take current pair if possible
                if (pairs > 0) {
                    dp[i][j][pairs] = Math.max(
                        dp[i][j][pairs],
                        dp[i-1][j-1][pairs-1] + nums1[i-1] * nums2[j-1]
                    );
                }
            }
        }
    }
    
    return dp[n][m][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析结果
时间复杂度O(n × m × k)
空间复杂度O(n × m × k)

其中 n 和 m 分别是两个数组的长度。记忆化搜索确保每个状态只计算一次，总共有 n × m × k 个状态。