[LeetCode] 64. Minimum Path Sum

Problem : https://leetcode.com/problems/minimum-path-sum/

This problem is similar to 62. Unique Paths

Below implementation uses top-down processing to calculate the minPathSum of the right-bottom position.

Time Complexity :  O ( Row * Column )

Space Complexity : O ( 1 )

from functools import lru_cache

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        @lru_cache(maxsize=None)
        def dfs(i, j):
            if i - 1 >= 0 and j - 1 >= 0:
                return min(dfs(i - 1, j), dfs(i, j - 1)) + grid[i][j]
            
            if i - 1 >= 0:
                return dfs(i - 1, j) + grid[i][j]
            
            if j - 1 >= 0:
                return dfs(i, j - 1) + grid[i][j]
            
            return grid[i][j]
        
        
        row = len(grid)
        column = len(grid[0])
        return dfs(row - 1, column - 1)

The bottom-up solution:

class Solution {
    public int minPathSum(int[][] grid) {
        int ROW = grid.length;
        int COLUMN = grid[0].length;
        
        int[][] dp = new int[ROW][COLUMN];
        
        dp[0][0] = grid[0][0];
        
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COLUMN; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                
                dp[i][j] = grid[i][j] + Math.min(i-1>=0 ? dp[i-1][j] : Integer.MAX_VALUE, j-1>=0 ? dp[i][j-1] : Integer.MAX_VALUE);
            }
        }
        
        return dp[ROW-1][COLUMN-1];
    }
}

Edited on 11/25/2021. Add the bottom-up solution.