064. 最小路径和.js

/**
 * Created by admin on 2018/5/20.
 */
/**给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 *
 * 输入:
 * [
 *  [1,3,1],
 *  [1,5,1],
 *  [4,2,1]
 * ]
 * 输出: 7
 * 解释: 因为路径 1→3→1→1→1 的总和最小。
 */

/**可以对空间复杂度进行优化，因为每次只需要前一层的最小路径
 * 所以可以优化到 O(n)
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  if (grid.length === 0) return 0;
  let map = [];

  let i = grid.length - 1;
  let j = grid[0].length - 1;

  while (i >= 0 && j >= 0) {
    if (!map[i]) {
      map[i] = [];
    }

    if (i === grid.length - 1 && j === grid[0].length - 1) {
      map[i][j] = grid[i][j];
    } else if (i === grid.length - 1) {
      map[i][j] = grid[i][j] + map[i][j + 1];
    } else if (j === grid[0].length - 1) {
      map[i][j] = grid[i][j] + map[i + 1][j];
    } else {
      map[i][j] = grid[i][j] + Math.min(map[i + 1][j], map[i][j + 1]);
    }

    j === 0 ? (j = grid[0].length - 1, i--) : j--;
  }

  console.log(map)
  return map[0][0];
};


// let arr = [
//   [1, 1, 1, 1, 1],
//   [2, 2, 2, 2, 1],
//   [0, 2, 2, 2, 1],
//   [0, 2, 2, 2, 1],
//   [0, 0, 0, 2, 1],
// ];

let arr = [
  [9, 9, 0, 8, 9, 0, 5, 7, 2, 2, 7, 0, 8, 0, 2, 4, 8],
  [4, 4, 2, 7, 6, 0, 9, 7, 3, 2, 5, 4, 6, 5, 4, 8, 7],
  [4, 9, 7, 0, 7, 9, 2, 4, 0, 2, 4, 4, 6, 2, 8, 0, 7],
  [7, 7, 9, 6, 6, 4, 8, 4, 8, 7, 9, 4, 7, 6, 9, 6, 5],
  [1, 3, 7, 5, 7, 9, 7, 3, 3, 3, 8, 3, 6, 5, 0, 3, 6],
  [7, 1, 0, 7, 5, 0, 6, 6, 5, 3, 2, 6, 0, 0, 9, 5, 7],
  [6, 5, 6, 3, 8, 1, 8, 6, 4, 4, 3, 4, 9, 9, 3, 3, 1],
  [1, 0, 2, 9, 7, 9, 3, 1, 7, 5, 1, 8, 2, 8, 4, 7, 6],
  [9, 6, 7, 7, 4, 1, 4, 0, 6, 5, 1, 9, 0, 3, 2, 1, 7],
  [2, 0, 8, 7, 1, 7, 4, 3, 5, 6, 1, 9, 4, 0, 0, 2, 7],
  [9, 8, 1, 3, 8, 7, 1, 2, 8, 3, 7, 3, 4, 6, 7, 6, 6],
  [4, 8, 3, 8, 1, 0, 4, 4, 1, 0, 4, 1, 4, 4, 0, 3, 5],
  [6, 3, 4, 7, 5, 4, 2, 2, 7, 9, 8, 4, 5, 6, 0, 3, 9],
  [0, 4, 9, 7, 1, 0, 7, 7, 3, 2, 1, 4, 7, 6, 0, 0, 0]
  ];    //77

console.log(minPathSum(arr))