leetcode “64. minimum path sum”

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];
}
}