3742. Maximum Path Score in a Grid

You are given an m x n grid where each cell contains one of the values 0, 1, or 2. You are also given an integer k.

You start from the top-left corner (0, 0) and want to reach the bottom-right corner (m - 1, n - 1) by moving only right or down.

Each cell contributes a specific score and incurs an associated cost, according to their cell values:

• 0: adds 0 to your score and costs 0.
• 1: adds 1 to your score and costs 1.
• 2: adds 2 to your score and costs 1.

Return the maximum score achievable without exceeding a total cost of k, or -1 if no valid path exists.

Note: If you reach the last cell but the total cost exceeds k, the path is invalid.

class Solution {
public:
    int maxPathScore(vector<vector<int>>& grid, int k) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<vector<int>>> dp(n,vector<vector<int>>(m, vector<int>(k+1, INT_MIN)));
        dp[0][0][0] = 0;
        for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) for(int turn = 0; turn <= k; turn++) {
            if(i + 1 < n) {
                int nextTurn = turn + (!!grid[i+1][j]);
                if(nextTurn <= k) {
                    dp[i+1][j][nextTurn] = max(dp[i+1][j][nextTurn], dp[i][j][turn] + grid[i+1][j]);
                }
            }
            if(j + 1 < m) {
                int nextTurn = turn + (!!grid[i][j+1]);
                if(nextTurn <= k) {
                    dp[i][j+1][nextTurn] = max(dp[i][j+1][nextTurn], dp[i][j][turn] + grid[i][j+1]);
                }
            }
        }
        int res = -1;
        for(int turn = 0; turn <= k; turn++) res = max(res, dp[n-1][m-1][turn]);
        return res;
    }
};