两只老鼠吃奶酪的最大得分 - 算法题解

两只老鼠吃奶酪的最大得分 - 算法题解

题目描述：

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。

下标为 i 处的奶酪被吃掉的得分为：

• 如果第一只老鼠吃掉，则得分为 'reward1[i]' 。
• 如果第二只老鼠吃掉，则得分为 'reward2[i]' 。

给你一个正整数数组 'reward1' ，一个正整数数组 'reward2' ，和一个非负整数 k 。

请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。

示例 1：

输入：'reward1' = [1,1,3,4], 'reward2' = [4,4,1,1], k = 2 输出：15 解释：这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。 总得分为 4 + 4 + 3 + 4 = 15 。 15 是最高得分。

代码实现：

class Solution {
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int n = reward1.length;
        int[][] dp = new int[n+1][k+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                // 第一只老鼠吃i-1块奶酪，第二只老鼠吃j-1块奶酪
                int score = reward1[i-1] + reward2[j-1];
                // 第一只老鼠吃i-1块奶酪，第二只老鼠吃j-2块奶酪
                int option1 = dp[i-1][j-1];
                // 第一只老鼠吃i-2块奶酪，第二只老鼠吃j-1块奶酪
                int option2 = dp[i-1][j];
                // 第一只老鼠和第二只老鼠分别吃i-1块和j-1块奶酪
                int option3 = dp[i][j-1];
                // 选最大的得分作为dp[i][j]
                dp[i][j] = Math.max(Math.max(option1, option2), option3) + score;
            }
        }
        return dp[n][k];
    }
}

算法解析：

本题可以使用动态规划解决。定义 dp[i][j] 表示第一只老鼠吃掉前 i 块奶酪，第二只老鼠吃掉前 j 块奶酪的情况下，最大得分。

状态转移方程为：

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + reward1[i-1] + reward2[j-1]

其中，reward1[i-1] + reward2[j-1] 表示当前两只老鼠分别吃掉第 i 块和第 j 块奶酪的得分。

最终结果为 dp[n][k]。

复杂度分析：

• 时间复杂度：O(n * k)，其中 n 为奶酪数量，k 为第一只老鼠需要吃的奶酪数量。
• 空间复杂度：O(n * k)，用于存储动态规划数组。