动态规划之Minimum Path Sum

题目描述如下：

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]; 
    }

}