LeetCode link

first thought

  • use dp from top left add to bottom right.
  • can be solved by using only a 1d array

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length < 1 || grid[0].length < 1) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        int[] sum = new int[col];
        sum[0] = grid[0][0];
        for (int i = 1; i < col; i++) {
            sum[i] = grid[0][i] + sum[i - 1];
        }
        for (int i = 1; i < row; i++) {
            sum[0] = sum[0] + grid[i][0];
            for (int j = 1; j < col; j++) {
                sum[j] = Math.min(sum[j - 1], sum[j]) + grid[i][j];
            }
        }
        return sum[col - 1];
    }
}