23.03.27 Today’s Leetcode

64. Minimum Path Sum (medium)

DP Approach

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[math.inf for i in range(n)] for j in range(m)]
        dp[0][0] = grid[0][0]
        for x in range(m):
            for y in range(n):
                if x > 0:
                    dp[x][y] = min(dp[x][y], dp[x - 1][y] + grid[x][y])
                if y > 0:
                    dp[x][y] = min(dp[x][y], dp[x][y - 1] + grid[x][y])
        print(dp)
        return dp[-1][-1]

2304. Minimum Path Cost in a Grid (medium)

class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[math.inf for _ in range(n)] for j in range(m)]
        for i in range(n):
            dp[0][i] = grid[0][i]
        
        print(dp[0])
        for i in range(1, m):
            for j in range(n):
                for p in range(n):
                    dp[i][j] = min(dp[i][j], dp[i - 1][p] + moveCost[grid[i - 1][p]][j] + grid[i][j])

            # print(dp[i])
        return min(dp[-1])

174. Dungeon Game (hard)

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
        dp[m - 1][n] = dp[m][n - 1] = 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j], 1)
        return dp[0][0]

741. Cherry Pickup (hard)

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        
        @lru_cache(None)
        def count_rec(r1, c1, r2, c2):
            if r1 >= n or r2 >= n or c1 >= n or c2 >= n or grid[r1][c1] == -1 or grid[r2][c2] == -1:
                return -float('inf')
            
            if r1 == n - 1 and c1 == n - 1:
                return grid[r1][c1]
            
            cherries_here = grid[r1][c1] if r1 == r2 or c1 == c2 else grid[r1][c1] + grid[r2][c2]
            
            return cherries_here + max(
                count_rec(r1 + 1, c1, r2 + 1, c2), 
                count_rec(r1 + 1, c1, r2, c2 + 1), 
                count_rec(r1, c1 + 1, r2 + 1, c2), 
                count_rec(r1, c1 + 1, r2, c2 + 1)
            )
        
        return max(count_rec(0, 0, 0, 0), 0)