給定一個包含非負整數的 m?x?n?網格，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。

說明：每次只能向下或者向右移動一步。

示例:

輸入:
[
??[1,3,1],
? [1,5,1],
? [4,2,1]
]
輸出: 7
解釋: 因為路徑 1→3→1→1→1 的總和最小。

提交的代碼：class Solution {
? ? public int minPathSum(int[][] grid) {
? ? ? ? ? ?int i,j;
? ? ? ? int m = grid.length;
? ? ? ? int n = grid[0].length;
? ? ? ? int[][] dp = new int[m][n];
? ? ? ? dp[0][0] = grid[0][0];
? ? ? ? for(i=0;i<m;i++)
? ? ? ? {
? ? ? ? ?? ?for(j=0;j<n;j++)
? ? ? ? ?? ?{
? ? ? ? ?? ??? ?if(i==0&&j>0)
? ? ? ? ?? ??? ?{
? ? ? ? ?? ??? ??? ?dp[i][j]=dp[i][j-1]+grid[i][j];
? ? ? ? ?? ??? ?}
? ? ? ? ?? ??? ?if(j==0&&i>0)
? ? ? ? ?? ??? ?{
? ? ? ? ?? ??? ??? ?dp[i][j]=dp[i-1][j]+grid[i][j];
? ? ? ? ?? ??? ?}
? ? ? ? ?? ??? ?if(i!=0&&j!=0)
? ? ? ? ?? ??? ?{
? ? ? ? ?? ??? ??? ?dp[i][j]=java.lang.Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j];
? ? ? ? ?? ??? ?}
? ? ? ? ?? ?}
? ? ? ? }
? ? ? ? return dp[m-1][n-1];
? ? }
}

?

完整代碼：

public class Solution64 {
?? ?public static int minPathSum(int[][] grid) {
? ? ? ? int i,j;
? ? ? ? int m = grid.length;
? ? ? ? int n = grid[0].length;
? ? ? ? int[][] dp = new int[m][n];
? ? ? ? dp[0][0] = grid[0][0];
? ? ? ? for(i=0;i<m;i++)
? ? ? ? {
? ? ? ? ?? ?for(j=0;j<n;j++)
? ? ? ? ?? ?{
? ? ? ? ?? ??? ?if(i==0&&j>0)
? ? ? ? ?? ??? ?{
? ? ? ? ?? ??? ??? ?dp[i][j]=dp[i][j-1]+grid[i][j];
? ? ? ? ?? ??? ?}
? ? ? ? ?? ??? ?if(j==0&&i>0)
? ? ? ? ?? ??? ?{
? ? ? ? ?? ??? ??? ?dp[i][j]=dp[i-1][j]+grid[i][j];
? ? ? ? ?? ??? ?}
? ? ? ? ?? ??? ?if(i!=0&&j!=0)
? ? ? ? ?? ??? ?{
? ? ? ? ?? ??? ??? ?dp[i][j]=java.lang.Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j];
? ? ? ? ?? ??? ?}
? ? ? ? ?? ?}
? ? ? ? }
? ? ? ? return dp[m-1][n-1];
? ? }
?? ?public static void main(String[] args)
?? ?{
?? ??? ?int[][] a = {{1,3,1},{1,5,1},{4,2,1}};
?? ??? ?System.out.println(minPathSum(a));
?? ?}
}
?

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的动态规划--Leetcode64.最小路径和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。