老鼠吃奶酪的最大得分 - 动态规划算法详解

老鼠吃奶酪的最大得分 - 动态规划算法详解

问题描述:

有两只老鼠和 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][k + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                for (int t = 0; t <= k; t++) {
                    dp[i][j][t] = dp[i - 1][j][t]; // 这块奶酪不被吃
                    if (j > 0) {
                        dp[i][j][t] = Math.max(dp[i][j][t], dp[i - 1][j - 1][t] + reward1[i - 1]); // 老鼠1吃这块奶酪
                    }
                    if (t > 0) {
                        dp[i][j][t] = Math.max(dp[i][j][t], dp[i - 1][j][t - 1] + reward2[i - 1]); // 老鼠2吃这块奶酪
                    }
                }
            }
        }
        return dp[n][k][k];
    }
}

思路:

动态规划。

• dp[i][j][t] 表示前 i 个奶酪中，老鼠1吃了 j 块，老鼠2吃了 t 块时，老鼠1的最大得分。

• 状态转移方程为：

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

其中 dp[i-1][j][t] 表示这块奶酪不被吃；dp[i-1][j-1][t]+reward1[i-1] 表示老鼠1吃这块奶酪；dp[i-1][j][t-1]+reward2[i-1] 表示老鼠2吃这块奶酪。

• 最终答案为 dp[n][k][k]。

时间复杂度: O(nkk)，空间复杂度：O(nkk)。

代码解释:

1. 定义三维数组 dp 来存储状态，其中 dp[i][j][t] 表示前 i 个奶酪中，老鼠1吃了 j 块，老鼠2吃了 t 块时，老鼠1的最大得分。
2. 遍历所有奶酪，对于每个奶酪，有三种情况：
   • 不吃这块奶酪：dp[i][j][t] = dp[i - 1][j][t]
   • 老鼠1吃这块奶酪：dp[i][j][t] = Math.max(dp[i][j][t], dp[i - 1][j - 1][t] + reward1[i - 1])
   • 老鼠2吃这块奶酪：dp[i][j][t] = Math.max(dp[i][j][t], dp[i - 1][j][t - 1] + reward2[i - 1])
3. 最终答案为 dp[n][k][k]，即所有奶酪中老鼠1吃了 k 块，老鼠2也吃了 k 块时，老鼠1的最大得分。

总结:

本题可以使用动态规划算法解决，时间复杂度为 O(nkk)，空间复杂度也为 O(nkk)。代码实现较为简洁，但需要注意状态转移方程的理解和实现。