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

题目描述如下：

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

很典型的dp题目，首先注意只能向右或向下移动；根据这个条件很容易得出递推关系式为dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];

为了便于计算dp的维度为dp[m+1][n+1]，所以实际的关系式为dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];

注意：第一行第一列单独求出；

代码如下：

public class Solution {

    public int minPathSum(int[][] grid) { int m = grid.length; int n = 0; if(m >= 0) n = grid[0].length; int[][] dp = new int[m + 1][n + 1]; //cal the first col for(int i = 1; i <= m; i++) dp[i][1] = dp[i - 1][1] + grid[i - 1][0]; //cal the first row for(int j = 1; j <= n; j++) dp[1][j] = dp[1][j - 1] + grid[0][j - 1]; for(int i = 2; i <= m; i++) for(int j = 2; j <= n; j++) dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];        return dp[m][n];      } }

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