题目描述

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

示例：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7

题目分析

动态规划
设 dp[i][j] 表示移动至 i, j 所需的最小总和，则 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
可以将空间优化为一维， dp[j] = min(dp[j], dp[j-1]) + grid[i][j]。

时间复杂度 O(m * n)

Java

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];
    dp[0] = grid[0][0];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) {
                continue;
            }
            int left = j >= 1 ? dp[j - 1] : Integer.MAX_VALUE;
            int up = i >= 1 ? dp[j] : Integer.MAX_VALUE;
            dp[j] = Math.min(left, up) + grid[i][j];
        }
    }
    return dp[n - 1];
}

Kotlin

fun minPathSum(grid: Array<IntArray>): Int {
    val m = grid.size
    val n = grid[0].size
    val dp = IntArray(n)
    dp[0] = grid[0][0]
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (i == 0 && j == 0) continue
            dp[j] = min(if (i >= 1) dp[j] else Int.MAX_VALUE, if (j >= 1) dp[j - 1] else Int.MAX_VALUE) + grid[i][j]
        }
    }
    return dp[n - 1]
}