最大得分奶酪分配：两只老鼠，不同奶酪，如何获得最大收益？

两只老鼠和 n 块不同类型的奶酪，如何获得最大收益？

有两只老鼠和 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[][] rewards = new int[n][2];
        for (int i = 0; i < n; i++) {
            rewards[i][0] = reward1[i];
            rewards[i][1] = reward2[i];
        }
        Arrays.sort(rewards, (a, b) -> (b[0] + b[1]) - (a[0] + a[1]));

        // dp[i][j] 表示第一只老鼠吃掉 j 块奶酪，且第 i 块奶酪被第一只老鼠吃掉时的最大得分
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                // 不吃第 i 块奶酪
                dp[i][j] = dp[i - 1][j];
                // 吃第 i 块奶酪
                if (j >= 1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + rewards[i - 1][0]);
                }
            }
        }

        // 计算第二只老鼠吃掉剩下的奶酪的最大得分
        int maxReward2 = 0;
        int pointer = k;
        for (int i = k; i < n; i++) {
            maxReward2 += rewards[i][1];
            pointer++;
        }

        // 返回第一只老鼠吃掉 k 块奶酪，第二只老鼠吃掉剩下的奶酪时的最大得分
        return dp[n][k] + maxReward2;
    }
}

思路：

对于第一只老鼠吃掉的 'k' 块奶酪，对应的第二只老鼠吃掉剩下的奶酪，所以可以枚举第一只老鼠吃掉的 'k' 块奶酪，然后求出第二只老鼠吃掉剩下的奶酪的最大得分。最后将两者相加即可。

具体实现时，可以先将两个数组按照奶酪得分从大到小排序，然后用一个指针记录第二只老鼠吃到了哪一块奶酪，每次选择第一只老鼠吃掉一个奶酪时，将指针往后移动，直到指针指向的奶酪不能被第二只老鼠吃掉为止。

代码解析：

排序：首先将 'reward1' 和 'reward2' 数组按照奶酪得分从大到小排序，并将其组合到一个二维数组 'rewards' 中，方便后续操作。
动态规划：使用一个二维数组 'dp' 来记录第一只老鼠吃掉 'j' 块奶酪，且第 'i' 块奶酪被第一只老鼠吃掉时的最大得分。
状态转移方程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + rewards[i - 1][0])，表示两种选择：
- 不吃第 'i' 块奶酪，则最大得分与上一行相同。
- 吃第 'i' 块奶酪，则最大得分等于上一行上一列的最大得分加上吃掉第 'i' 块奶酪的得分。
计算第二只老鼠的最大得分：使用一个指针记录第二只老鼠吃到了哪一块奶酪，从第一只老鼠吃掉的 'k' 块奶酪开始，一直往后遍历，将所有能够被第二只老鼠吃掉的奶酪的得分累加起来。
返回结果：最后将第一只老鼠吃掉 'k' 块奶酪的最大得分和第二只老鼠吃掉剩下的奶酪的最大得分相加，即为最终的答案。

优化建议：

可以使用二分查找优化第二只老鼠吃掉剩下奶酪的最大得分计算，减少时间复杂度。
可以使用滚动数组优化空间复杂度，将二维数组 'dp' 降为一维数组。