面试算法99:最小路径之和

发布时间:2024年01月08日

题目

在一个m×n(m、n均大于0)的格子中,每个位置都有一个数字。一个机器人每步只能向下或向右,请计算它从格子的左上角到达右下角的路径的数字之和的最小值。例如,从图14.8中3×3的格子的左上角到达右下角的路径的数字之和的最小值是8,图中数字之和最小的路径用灰色背景表示。
在这里插入图片描述

分析

由于这个题目并没有要求列出所有的路径,而是求路径的数字之和的最小值,也就是求最优解,因此这个问题适合应用动态规划求解。
应用动态规划解决问题的关键在于找出状态转移方程。用函数f(i,j)表示从格子的左上角坐标为(0,0)的位置(用grid[0][0]表示)出发到达坐标为(i,j)的位置(用grid[i][j]表示)的路径的数字之和的最小值。如果格子的大小为m×n,那么f(m-1,n-1)就是问题的解。

public class Test {
    public static void main(String[] args) {
        int[][] grid = {
            {1, 3, 1},
            {2, 5, 2},
            {3, 4, 1}
        };
        int result = minPathSum(grid);
        System.out.println(result);

    }

    public static int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for (int j = 1; j < grid[0].length; j++) {
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }

        for (int i = 1; i < grid.length; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
            for (int j = 1; j < grid[0].length; j++) {
                int prev = Math.min(dp[i - 1][j], dp[i][j - 1]);
                dp[i][j] = grid[i][j] + prev;
            }
        }

        return dp[grid.length - 1][grid[0].length - 1];
    }
}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135452780
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。