LeetCode <dp>64. Minimum Path Sum

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

    int sum = 0;
    int [][] sss ;
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length ==0) return 0;
        sss = new int[grid.length][grid[0].length];
        return minPathSum_recursion(grid,0,0);
    }

 
    public int minPathSum_recursion(int[][] grid,int m ,int n) {
        if (m==grid.length-1) {
            int a = 0;
            for (int i = n;i<grid[0].length;i++){
                a = a + grid[m][i];
            }
            return a;
        }

        if (n == grid[0].length-1) {
            int b = 0;
            for (int i = m;i<grid.length;i++){
                b = b + grid[i][n];
            }
            return b;
        }
        if (sss[m][n] == 0){
            sss[m][n] = sum + grid[m][n] + Math.min(minPathSum_recursion(grid,m+1,n),minPathSum_recursion(grid,m,n+1));
        }
        return sss[m][n];
    }

    public int minPathSum(int[][] grid) {
        if (grid == null ||grid.length ==0|| grid[0].length ==0) return 0;
        int min = Math.min(grid.length,grid[0].length);
        int max = Math.max(grid.length,grid[0].length);
        int [] arr = new int[min];
        boolean rowlonger = grid.length == max; // 行数大于列数
        arr[0] = grid[0][0];
        for (int i = 1;i<min;i++){
            arr[i] = arr[i-1] + (rowlonger?grid[0][i]:grid[i][0]);
        }

        for (int i=1;i<max;i++){
            arr[0] = arr[0]+(rowlonger?grid[i][0]:grid[0][i]);
            for (int j = 1; j<min;j++){
                arr[j] = Math.min(arr[j-1],arr[j])+(rowlonger?grid[i][j]:grid[j][i]);
            }
        }
        return arr[min-1];
    }