1 解题思想
嗯,我做的时候是乱序,写的时候才发现,这完全就是和62 63一个德行啊,做法还是基本一样,不同的是,62 63是求和,64这里是取每一步的最小和。
标准的动态规划,至于怎么走,请看62 63:
Unique Paths 路径搜寻 解题报告
Unique Paths II 路径搜寻2 解题报告
2 原题
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.
3 AC解
public class Solution {
/**
* 很标准的动态规划的题目
* */
public int minPathSum(int[][] grid) {
if(grid.length==0 || grid[0].length==0)
return 0;
int m=grid.length;
int n=grid[0].length;
int dp[][]=new int[m][n];
int top,left;
int i=0,j;
dp[0][0]=grid[0][0];
for( j=1;j<n;j++){
dp[i][j]=dp[i][j-1]+grid[i][j];
}
for( j=1;j<m;j++){
dp[j][i]=dp[j-1][i]+grid[j][i];
}
for( i=1;i<m;i++){
for( j=1;j<n;j++){
top=Integer.MAX_VALUE;
left=Integer.MAX_VALUE;
top=dp[i-1][j];
left=dp[i][j-1];
dp[i][j]=Math.min(top,left)+grid[i][j];
}
}
return dp[m-1][n-1];
}
}
版权声明:本文为MebiuW原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。