Online Judge►LeetCode

[LeetCode] 64 - Minimum Path Sum

題意

給一個 m x n 填滿非負數的矩陣，從左上方開始往右下走且每一步只能往右或往下走，求最小數字總和。

解法

DP。

1
2
3
dp(i,j) = dp[i][j-1] + grid[i][j] if i = 0
	= dp[i-1][j] + grid[i][j] if j = 0
	= min(dp[i-1][j], dp[i][j-1]) + grid[i][j] else

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array.apply(null, Array(m+1)).map(row => new Array(n+1).fill(0));
  for ( let i = 1 ; i < dp.length ; i ++ ){
    for ( let j = 1 ; j < dp[i].length ; j ++ ){
      if ( i === 1 ) dp[i][j] = dp[i][j-1] + grid[i-1][j-1];
      else if ( j === 1 ) dp[i][j] = dp[i-1][j] + grid[i-1][j-1];
      else dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]; 
    }
  }
  return dp[m][n];
};