题目

LeetCode.64.最小路径和（中等）

给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

题解

要达到右下角[m, n]，只有两种可能：

从上边[m - 1, n]来
从左边[m, n - 1]来

[m - 1, n]怎么达到？按道理有3条路径，从上来、从左来、从下来。
但是从下来不考虑，因为从起点到终点的路径是要从上到下的，如果从下面上来最后还是要下去，路径和增大了，多此一举。

同理中间的格子，如果是从右边过来也是多此一举，因为起点到终点的路径是要从左到右的。

所以对于每个格子，只考虑从上和从左过来。

某个状态的问题就拆解为了子问题+有限步骤，并且符合最优子结构，也无后效性。而且有大量重叠子问题，比如到达[i, j]格的路径和，在计算到达[i + 1][j]路径数和到达[i][j + 1]路径和时都会用到。

符合使用动态规划所有条件。

状态转移方程
设dp[i][j]为达到方格[i, j]的路径和。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

边界处理
[0, 0]格没有左边和上面，路径和就是当前元素值。
第一行所有格子没有上面，都只能从左边过来，路径和从左边累加。
第一列所有格子没有左边，都只能从上边过来，路径和从右边累加。

复杂度
要遍历所有网格，才能找到最少路径和，所以时间无法省略。
时间复杂度$O(mn)$。

如果记录达到所有格子的路径和，空间复杂度$O(mn)$。

class Solution {
    fun minPathSum(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val dp = Array(m) { IntArray(n) { 0 } }
        dp[0][0] = grid[0][0]
        for (i in 1 until m) dp[i][0] = dp[i - 1][0] + grid[i][0]
        for (j in 1 until n) dp[0][j] = dp[0][j - 1] + grid[0][j]
        for (i in 1 until m) {
            for (j in 1 until n) {
                dp[i][j] = grid[i][j] + minOf(dp[i - 1][j], dp[i][j - 1])
            }
        }
        return dp[m - 1][n - 1]
    } 
}

空间优化

由于每个格子的路径数只会从上面和左边的路径和推导而来，而且只会读取上面和左边的项，所以不需要记录所有格子的路径数。

那么要记录多少个格子的路径和？
因为终点格子可以从左边过来，所以要记录左边所有的格子的路径和，所以记录一行是必须的。读取上一行格子的路径和，直接读取之前记录的行就行了。
所以只需要记录一行格子的路径和。

class Solution {
    fun minPathSum(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        // 存储一行格子的路径数
        val dp = IntArray(n) { 0 }
        dp[0] = grid[0][0]
        // 第一行不能从上边过来，特殊处理
        for (j in 1 until n) dp[j] = dp[j - 1] + grid[0][j]
        for (i in 1 until m) {
            for (j in 0 until n) {
                // dp[j]是上面格子的路径数
                // dp[j - 1]是左边格子的路径数
                dp[j] = if (j == 0) grid[i][j] + dp[j]
                else grid[i][j] + minOf(dp[j], dp[j - 1])
            }
        }
        return dp[n - 1]
    } 
}

时间复杂度$O(mn)$
空间复杂度$O(n)$

如果m < n，也可以做到$O(m)$空间复杂度，交换行列把矩阵转置，并不影响结果，再递推就行。