64.最小路径和

题目描述

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

示例 1:

输入: grid = [[1,3,1],[1,5,1],[4,2,1]]
输出: 7

示例 2:

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

解题思路：动态规划

设 f[i][j] 为到达 (i, j) 的路径最小和。只能从上方 (i-1, j) 或左方 (i, j-1) 来到 (i, j)，因此：

f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i][j]。

边界：f[0][0] = grid[0][0]；第一行只能从左累加，第一列只能从上累加。

代码实现（二维数组）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        Solution solution = new Solution();
        int result = solution.minPathSum(grid);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] f = new int[m][n];
        f[0][0] = grid[0][0];
        for (int j = 1; j < n; j++) { f[0][j] = f[0][j - 1] + grid[0][j]; }
        for (int i = 1; i < m; i++) { f[i][0] = f[i - 1][0] + grid[i][0]; }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
            }
        }
        return f[m - 1][n - 1];
    }
}

代码实现（空间优化，滚动一维）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        Solution solution = new Solution();
        int result = solution.minPathSum(grid);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    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 j = 1; j < n; j++) { dp[j] = dp[j - 1] + grid[0][j]; }
        for (int i = 1; i < m; i++) {
            dp[0] += grid[i][0];
            for (int j = 1; j < n; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        return dp[n - 1];
    }
}

复杂度分析

• 时间复杂度：O(mn)。
• 空间复杂度：O(mn)（二维），优化为 O(n)（一维滚动）。

只允许右或下移动，局部最优累加成全局最优，边界行列先行初始化后再推进转移即可。