题目描述如下:
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];
}
}