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

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

假设有两只老鼠和 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 = 0; j <= k; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + Math.max(reward1[i - 1], reward2[i - 1]);
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + reward1[i - 1]);
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + reward2[i - 1]);
                }
            }
        }
        return dp[n][k];
    }
}

算法分析：

1. 状态定义: 使用二维数组 'dp[i][j]' 表示前 i 块奶酪中，第一只老鼠吃掉 j 块奶酪所能获得的最大得分。
2. 状态转移方程: 对于第 i 块奶酪，有两种选择：
   • 第一只老鼠吃掉： 'dp[i][j] = dp[i - 1][j - 1] + reward1[i - 1]'
   • 第二只老鼠吃掉： 'dp[i][j] = dp[i - 1][j] + reward2[i - 1]' 我们要选择两种方案中得分更高的那个。
3. 边界条件: 当 j 为 0 时，表示第一只老鼠没有吃任何奶酪，此时最大得分即为前 i 块奶酪中，两支老鼠分别选择得分更高的奶酪所能获得的总得分。
4. 最终结果: 返回 'dp[n][k]' ，表示前 n 块奶酪中，第一只老鼠吃掉 k 块奶酪所能获得的最大得分。

总结：

本问题可以使用动态规划算法解决，通过定义状态和转移方程，我们可以得到最终的答案。

希望本文能够帮助你更好地理解该问题，并掌握动态规划算法的应用。