Minimum Path Sum

Description

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

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

Solution(javascript)

/*
 * @lc app=leetcode id=64 lang=javascript
 *
 * [64] Minimum Path Sum
 */

// @lc code=start
// /** 1: Top-down approach
//  * @param {number[][]} grid
//  * @return {number}
//  */
// export const minPathSum = (grid = []) => {
//   const memo = {}
//   const aux = (row, column) => {
//     const key = `${row}-${column}`
//     if (memo[key] !== undefined) {
//       return memo[key]
//     }
//     if (row === grid.length - 1 && column === grid[row].length - 1) {
//       return grid[row][column]
//     }
//     if (row > grid.length - 1 || column > grid[row].length - 1) {
//       return Infinity
//     }
//     memo[key] = grid[row][column] + Math.min(
//       aux(row + 1, column),
//       aux(row, column + 1),
//     )
//     return memo[key]
//   }
//   return aux(0, 0)
// }


/** 2: Bottom-up approach
 * @param {number[][]} grid
 * @return {number}
 */
const minPathSum = (grid = []) => {
  let memo = new Array(grid[0].length+1).fill(Infinity)
  for (let row = grid.length - 1; row >= 0; row--) {
    const current = new Array(grid[0].length+1).fill(Infinity)
    for (let column = grid[row].length - 1; column >= 0; column--) {
      if (row === grid.length - 1 && column === grid[row].length - 1) {
        current[column] = grid[row][column]
      } else {
        current[column] = Math.min(
          memo[column],
          current[column + 1]
        ) + grid[row][column]
      }
    }
      
    memo = current
  }
  return memo[0]
}

// @lc code=end