LeeCode-64.最小路径和

LeeCode题目概述

给定一个包含非负整数的 m * n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

• 事例1:

  输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
  输出：7
  解释：因为路径 1→3→1→1→1 的总和最小。

• 事例2:

  输入：grid = [[1,2,3],[4,5,6]]
  输出：12

解题思路

• 动态规划

由于路径的方向只能是向下或者向右，因此网格的第一行的每一个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。

// 原地处理[][]int
// 空间复杂度O1
// 时间复杂度O(mn)
func minPathSum(grid [][]int) int {
    // 处理 grid 为空的情况
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }
    // 行长度、列长度
    rows, columns := len(grid), len(grid[0])
    // 遍历，原地处理原[][]int
    for i := 0; i < rows; i++ {
        for j := 0; j < columns; j++ {
            // 如果为第一行第一列的位置不处理
            if i == 0 && j == 0 {
                continue
            } else if i == 0 && j > 0 {// 第一行的元素数值累加
                grid[i][j] = grid[i][j] + grid[i][j-1]
            } else if i > 0 && j == 0 {// 第一列的元素数值累加
                grid[i][j] = grid[i][j] + grid[i-1][j]
            } else {// 通过i-1和j-1的元素数值计算最小值
                value := 0
                // 最小值
                if grid[i-1][j] > grid[i][j-1] {
                    value = grid[i][j-1]
                } else {
                    value = grid[i-1][j]
                }
                grid[i][j] = grid[i][j] + value
            }
        }
    }
    // 最终结果
    return grid[rows-1][columns-1]
}