本文共 1604 字，大约阅读时间需要 5 分钟。

要解决这个问题，我们需要找到从二维数组的左上角到右下角的路径，使得路径上的所有数字之和最小。只能向右或向下移动。

分析

最开始，我认为可以使用贪婪算法来选择每一步的最优方向，但后来发现这种方法并不一定能找到全局最优解。于是，我转向动态规划的方法。动态规划可以帮助我们记录每个位置的最小路径和，从而确保找到全局最优解。

方法思路

解决代码

public class MinPathSum {    public static void main(String[] args) {        int[][] grid = {            {1, 3, 1},            {1, 5, 1},            {4, 2, 1}        };        int result = minPathSum(grid);        System.out.println(result);    }    public static int minPathSum(int[][] grid) {        int m = grid.length;        if (m == 0) return 0;        int n = grid[0].length;        if (n == 0) return 0;        int[][] dp = new int[m][n];        dp[0][0] = grid[0][0];        // 初始化第一行和第一列        for (int i = 0; i < n; i++) {            if (i > 0) {                dp[0][i] = dp[0][i - 1] + grid[0][i];            }        }        for (int i = 0; i < m; i++) {            if (i > 0) {                dp[i][0] = dp[i - 1][0] + grid[i][0];            }        }        // 填充剩余位置        for (int i = 1; i < m; i++) {            for (int j = 1; j < n; j++) {                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];            }        }        return dp[m - 1][n - 1];    }}

代码解释

这种方法确保了我们能够在O(m * n)的时间复杂度和O(m * n)的空间复杂度下找到最优解，适用于较大的网格。

转载地址：http://ordy.baihongyu.com/