Leetcode 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.

m x n 크기의 그리드가 주어진다. 각 칸에는 0, 1, 2 중 하나의 값이 들어 있다.
또한 정수 k가 주어진다.

당신은 왼쪽 위 모서리 (0, 0)에서 시작해서 오른쪽 아래 모서리 (m - 1, n - 1)까지 이동하려고 한다.

이동은 오직 아래쪽 또는 오른쪽으로만 할 수 있다.

각 칸은 값에 따라 점수를 더하고, 비용을 소모한다.

• 0: 점수에 0을 더하고, 비용은 0이다.
• 1: 점수에 1을 더하고, 비용은 1이다.
• 2: 점수에 2를 더하고, 비용은 1이다.

총 비용이 k를 초과하지 않도록 하면서 얻을 수 있는 최대 점수를 반환하라.

만약 유효한 경로가 없다면 -1을 반환하라.

참고: 마지막 칸에 도달하더라도 총 비용이 k를 초과하면 해당 경로는 유효하지 않다.

예시

입력: grid = [[0, 1], [2, 0]], k = 1

출력: 2

설명:

최적의 경로는 다음과 같다.

칸	grid[i][j]	점수	총점	비용	총 비용
(0, 0)	0	0	0	0	0
(1, 0)	2	2	2	1	1
(1, 1)	0	0	2	0	1

제한

• $1 \le m, n \le 200$
• $0 \le k \le 10^3$
• $grid[0][0] = 0$
• $0 \le grid[i][j] \le 2$

풀이법

전형적인 DP 풀이법으로 풀수 있다, 다만 탑다운으로 해결시 메모리 복잡도 에러가 나올수 있기 때문에 탑다운으로 해결하는것을 권장한다.

class Solution:
    def maxPathScore(self, grid: List[List[int]], k: int) -> int:
        ROW = len(grid)
        COL = len(grid[0])

        dp = [[[-1] * COL for _ in range(ROW)] for _ in range(k + 1)]

        dp[k][0][0] = 0

        for r in range(ROW):
            for c in range(COL):
                for budget in range(k, -1, -1):
                    if dp[budget][r][c] == -1:
                        continue

                    action = grid[r][c]

                    if action > 0:
                        if budget == 0:
                            continue

                    nxt = budget - 1 if action > 0 else budget

                    if r + 1 < ROW:
                        dp[nxt][r + 1][c] = max(
                            dp[nxt][r + 1][c], dp[budget][r][c] + action
                        )

                    if c + 1 < COL:
                        dp[nxt][r][c + 1] = max(
                            dp[nxt][r][c + 1], dp[budget][r][c] + action
                        )

        ans = -1

        for i in range(k, -1, -1):
            if dp[i][ROW - 1][COL - 1] == -1:
                continue

            if action > 0 and i == 0:
                break

            ans = max(ans, dp[i][ROW - 1][COL - 1] + action)

        return ans