commit ab95956f801403524c6fd1f7d6a904f5b26cadeb
parent fc5b3a59814cad2c25da9b0d1f2a3bf6e4a22a79
Author: Jack Sangdahl <jack@pngu.org>
Date: Wed, 29 Apr 2026 21:23:24 -0600
3742. maximum path score in a grid
Diffstat:
2 files changed, 119 insertions(+), 0 deletions(-)
diff --git a/max_path_score_grid.c b/max_path_score_grid.c
@@ -0,0 +1,73 @@
+// 3742. Maximum Path Score in a Grid
+#include "leetcode.h"
+
+/*
+ * 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 and want to reach the bottom right corner by moving on right or down.
+ * each cell contributes a specific score and incurs an associated cost. return
+ * the maximum score achievable without exciting 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.
+ */
+
+int maxPathScore(int **grid, int gridSize, int *gridColSize, int k) {
+ int n = gridColSize[0], m = gridSize;
+ int ***dp = (int ***)malloc(m * sizeof(int **));
+ for (int i = 0; i < m; i++) {
+ dp[i] = (int **)malloc(n * sizeof(int *));
+ for (int j = 0; j < n; j++) {
+ dp[i][j] = (int *)malloc((k + 1) * sizeof(int));
+ for (int c = 0; c <= k; c++)
+ dp[i][j][c] = INT_MIN;
+ }
+ }
+ dp[0][0][0] = 0;
+ for (int i = 0; i < m; i++)
+ for (int j = 0; j < n; j++)
+ for (int c = 0; c <= k; c++) {
+ if (dp[i][j][c] == INT_MIN)
+ continue;
+ if (i + 1 < m) {
+ int val = grid[i + 1][j];
+ int cost = !val ? 0 : 1;
+ if (c + cost <= k) {
+ int *target = &dp[i + 1][j][c + cost];
+ *target = fmax(*target, dp[i][j][c]);
+ }
+ }
+ if (j + 1 < n) {
+ int val = grid[i][j + 1];
+ int cost = !val ? 0 : 1;
+ if (c + cost <= k) {
+ int *target = &dp[i][j + 1][c + cost];
+ *target = fmax(*target, dp[i][j][c]);
+ }
+ }
+ }
+ int ans = INT_MIN;
+ for (int i = 0; i <= k; i++)
+ ans = fmax(ans, dp[m - 1][n - 1][i]);
+ for (int i = 0; i < m; i++) {
+ for (int j = 0; j < n; j++)
+ free(dp[i][j]);
+ free(dp[i]);
+ }
+ free(dp);
+ return ans < 0 ? -1 : ans;
+}
+
+int main() {
+ int g1i[2][2] = {{0, 1}, {2, 0}};
+ int g2i[2][2] = {{0, 1}, {1, 2}};
+ struct two_d_arr *g1 =
+ two_d_arr_init(ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+ struct two_d_arr *g2 =
+ two_d_arr_init(ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+ int r1 = maxPathScore(g1->arr, g1->row_size, g1->col_size, 1);
+ int r2 = maxPathScore(g2->arr, g2->row_size, g2->col_size, 1);
+ printf("%d\n", r1);
+ assert(r1 == 2);
+ printf("%d\n", r2);
+ assert(r2 == -1);
+}
diff --git a/max_path_score_grid.py b/max_path_score_grid.py
@@ -0,0 +1,46 @@
+# 3742. Maximum Path Score in a Grid
+from typing import List
+
+"""
+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 and want to reach the bottom right corner by moving on right or down.
+each cell contributes a specific score and incurs an associated cost. return
+the maximum score achievable without exciting 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:
+ def maxPathScore(self, grid: List[List[int]], k: int) -> int:
+ m, n = len(grid), len(grid[0])
+ dp = [[[float("-inf")] * (k + 1) for _ in range(n)] for _ in range(m)]
+ dp[0][0][0] = 0
+ for i in range(m):
+ for j in range(n):
+ for c in range(k + 1):
+ if dp[i][j][c] == float("-inf"):
+ continue
+ if i + 1 < m:
+ val = grid[i + 1][j]
+ cost = 0 if val == 0 else 1
+ if c + cost <= k:
+ dp[i + 1][j][c + cost] = max(
+ dp[i + 1][j][c + cost], dp[i][j][c] + val
+ )
+ if j + 1 < n:
+ val = grid[i][j + 1]
+ cost = 0 if val == 0 else 1
+ if c + cost <= k:
+ dp[i][j + 1][c + cost] = max(
+ dp[i][j + 1][c + cost], dp[i][j][c] + val
+ )
+ ans = max(dp[m - 1][n - 1])
+ return -1 if ans < 0 else ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxPathScore(grid=[[0, 1], [2, 0]], k=1))
+ print(obj.maxPathScore(grid=[[0, 1], [1, 2]], k=1))
