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

题目

在一个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];
    }
}