3742. Maximum Path Score in a Grid

/**
 * Problem: LeetCode 3742 - Maximum Path Score in a Grid
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.Arrays;

class Solution {
    public int maxPathScore(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int maxCost = Math.min(k, m + n - 1);

        int[][] dp = new int[n][maxCost + 1];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }

        int cost0 = grid[0][0] == 0 ? 0 : 1;
        int score0 = grid[0][0];
        if (cost0 <= maxCost) {
            dp[0][cost0] = score0;
        } else {
            return -1;
        }

        // Initialize first row
        for (int c = 1; c < n; c++) {
            int cost = grid[0][c] == 0 ? 0 : 1;
            int score = grid[0][c];
            for (int w = cost; w <= maxCost; w++) {
                if (dp[c - 1][w - cost] != -1) {
                    dp[c][w] = dp[c - 1][w - cost] + score;
                }
            }
        }

        // Process subsequent rows
        for (int r = 1; r < m; r++) {
            int[][] nextDp = new int[n][maxCost + 1];
            for (int[] row : nextDp) {
                Arrays.fill(row, -1);
            }

            for (int c = 0; c < n; c++) {
                int cost = grid[r][c] == 0 ? 0 : 1;
                int score = grid[r][c];

                for (int w = cost; w <= maxCost; w++) {
                    int best = -1;
                    if (dp[c][w - cost] != -1) {
                        best = Math.max(best, dp[c][w - cost]);
                    }
                    if (c > 0 && nextDp[c - 1][w - cost] != -1) {
                        best = Math.max(best, nextDp[c - 1][w - cost]);
                    }
                    if (best != -1) {
                        nextDp[c][w] = best + score;
                    }
                }
            }
            dp = nextDp;
        }

        int maxScore = -1;
        for (int w = 0; w <= maxCost; w++) {
            maxScore = Math.max(maxScore, dp[n - 1][w]);
        }
        return maxScore;
    }
}

"""
Problem: LeetCode 3742 - Maximum Path Score in a Grid
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def maxPathScore(self, grid: List[List[int]], k: int) -> int:
        m = len(grid)
        n = len(grid[0])
        max_cost = min(k, m + n - 1)

        dp = [[-1] * (max_cost + 1) for _ in range(n)]

        cost0 = 0 if grid[0][0] == 0 else 1
        score0 = grid[0][0]
        if cost0 <= max_cost:
            dp[0][cost0] = score0
        else:
            return -1

        for c in range(1, n):
            cost = 0 if grid[0][c] == 0 else 1
            score = grid[0][c]
            for w in range(cost, max_cost + 1):
                if dp[c - 1][w - cost] != -1:
                    dp[c][w] = dp[c - 1][w - cost] + score

        for r in range(1, m):
            next_dp = [[-1] * (max_cost + 1) for _ in range(n)]
            for c in range(n):
                cost = 0 if grid[r][c] == 0 else 1
                score = grid[r][c]
                for w in range(cost, max_cost + 1):
                    best = -1
                    if dp[c][w - cost] != -1:
                        best = max(best, dp[c][w - cost])
                    if c > 0 and next_dp[c - 1][w - cost] != -1:
                        best = max(best, next_dp[c - 1][w - cost])
                    if best != -1:
                        next_dp[c][w] = best + score
            dp = next_dp

        return max(dp[n - 1])

/**
 * Problem: LeetCode 3742 - Maximum Path Score in a Grid
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxPathScore(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        int maxCost = min(k, m + n - 1);

        vector<vector<int>> dp(n, vector<int>(maxCost + 1, -1));

        int cost0 = (grid[0][0] == 0 ? 0 : 1);
        int score0 = grid[0][0];
        if (cost0 <= maxCost) {
            dp[0][cost0] = score0;
        } else {
            return -1;
        }

        // First row
        for (int c = 1; c < n; c++) {
            int cost = (grid[0][c] == 0 ? 0 : 1);
            int score = grid[0][c];
            for (int w = cost; w <= maxCost; w++) {
                if (dp[c - 1][w - cost] != -1) {
                    dp[c][w] = dp[c - 1][w - cost] + score;
                }
            }
        }

        // Remaining rows
        for (int r = 1; r < m; r++) {
            vector<vector<int>> nextDp(n, vector<int>(maxCost + 1, -1));
            for (int c = 0; c < n; c++) {
                int cost = (grid[r][c] == 0 ? 0 : 1);
                int score = grid[r][c];

                for (int w = cost; w <= maxCost; w++) {
                    int best = -1;
                    if (dp[c][w - cost] != -1) {
                        best = max(best, dp[c][w - cost]);
                    }
                    if (c > 0 && nextDp[c - 1][w - cost] != -1) {
                        best = max(best, nextDp[c - 1][w - cost]);
                    }
                    if (best != -1) {
                        nextDp[c][w] = best + score;
                    }
                }
            }
            dp = move(nextDp);
        }

        int maxScore = -1;
        for (int w = 0; w <= maxCost; w++) {
            maxScore = max(maxScore, dp[n - 1][w]);
        }
        return maxScore;
    }
};

/**
 * Problem: LeetCode 3742 - Maximum Path Score in a Grid
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var maxPathScore = function(grid, k) {
    const m = grid.length;
    const n = grid[0].length;
    const maxCost = Math.min(k, m + n - 1);

    let dp = Array.from({ length: n }, () => new Int32Array(maxCost + 1).fill(-1));

    const cost0 = grid[0][0] === 0 ? 0 : 1;
    const score0 = grid[0][0];
    if (cost0 <= maxCost) {
        dp[0][cost0] = score0;
    } else {
        return -1;
    }

    // First row
    for (let c = 1; c < n; c++) {
        const cost = grid[0][c] === 0 ? 0 : 1;
        const score = grid[0][c];
        for (let w = cost; w <= maxCost; w++) {
            if (dp[c - 1][w - cost] !== -1) {
                dp[c][w] = dp[c - 1][w - cost] + score;
            }
        }
    }

    // Remaining rows
    for (let r = 1; r < m; r++) {
        const nextDp = Array.from({ length: n }, () => new Int32Array(maxCost + 1).fill(-1));
        for (let c = 0; c < n; c++) {
            const cost = grid[r][c] === 0 ? 0 : 1;
            const score = grid[r][c];

            for (let w = cost; w <= maxCost; w++) {
                let best = -1;
                if (dp[c][w - cost] !== -1) {
                    best = dp[c][w - cost];
                }
                if (c > 0 && nextDp[c - 1][w - cost] > best) {
                    best = nextDp[c - 1][w - cost];
                }
                if (best !== -1) {
                    nextDp[c][w] = best + score;
                }
            }
        }
        dp = nextDp;
    }

    let maxScore = -1;
    for (let w = 0; w <= maxCost; w++) {
        if (dp[n - 1][w] > maxScore) {
            maxScore = dp[n - 1][w];
        }
    }
    return maxScore;
};