LC 3363. Find the Maximum Number of Fruits Collected

https://tools.xxooooxx.org/su/VU7TFXpms

Tag: DP

class Solution {
public:
    vector<pair<int, int>> dir2 = {{1, -1}, {1, 0}, {1, 1}};
    vector<pair<int, int>> dir3 = {{-1, 1}, {0, 1}, {1, 1}};
    int maxCollectedFruits(vector<vector<int>>& fruits) {
        int n = fruits.size();
        int player1 = 0;
        for (int i = 0; i < n; i++) player1 += fruits[i][i];

        vector<vector<int>> player2(n, vector<int>(n, -1));
        player2[0][n - 1] = fruits[0][n - 1];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (player2[i][j] == -1) continue;
                for (auto [dr, dc]: dir2) {
                    int x = i + dr;
                    int y = j + dc;
                    if (x < 0 || y < 0 || x >= n || y >= n) continue;
                    if (y <= x) continue;
                    player2[x][y] = max(player2[x][y], player2[i][j] + fruits[x][y]);
                }
            }
        }
        player2[n - 1][n - 1] = max(player2[n - 2][n - 1], player2[n - 2][n - 2]);

        vector<vector<int>> player3(n, vector<int>(n, -1));
        player3[n - 1][0] = fruits[n - 1][0];
        for (int j = 0; j < n; j++) {
            for (int i = j + 1; i < n; i++) {
                if (player3[i][j] == -1) continue;
                for (auto [dr, dc]: dir3) {
                    int x = i + dr;
                    int y = j + dc;
                    if (x < 0 || y < 0 || x >= n || y >= n) continue;
                    if (x <= y) continue;
                    player3[x][y] = max(player3[x][y], player3[i][j] + fruits[x][y]);
                }
            }
        }
        player3[n - 1][n - 1] = max(player3[n - 1][n - 2], player3[n - 2][n - 2]);
        return player1 + player2[n - 1][n - 1] + player3[n - 1][n - 1];
    }
};

本題的重點在觀察，透過觀察可以發現其實三個玩家不會互相干擾，所以我們可以將每個玩家獨立計算。

玩家1: 由於題目的 n - 1 步的限制，所以此玩家只能走對角線
玩家2 與玩家3: 可以發現他們都不會跨過對角線，因為一旦跨過對角線就將無法在限定的步數內回到 (n - 1, n - 1) 這個座標。

知道以上資訊後就可以將每個玩家透過 DP 的方式分別計算結果。