美文网首页
最小路径和

最小路径和

作者: 二进制的二哈 | 来源:发表于2019-12-15 22:42 被阅读0次

    题目来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/minimum-path-sum

    给定一个包含非负整数的 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[][] dp = new int[grid.length][grid[0].length];
            //初始化左上角
            dp[0][0] = grid[0][0];
            //初始化最上边一行
            for (int i= 1;i<grid[0].length;i++){
                dp[0][i] = grid[0][i] + dp[0][i-1];
            }
            //初始化最左边一列
            for (int i= 1;i<grid.length;i++){
                dp[i][0] = grid[i][0] + dp[i-1][0];
            }
            for (int i=1;i<grid.length;i++){
                for (int j = 1;j<grid[0].length;j++){
                    //上边的数
                    int top = dp[i-1][j];
                    //左边的数
                    int left = dp[i][j-1];
                    dp[i][j] = Math.min(top,left) + grid[i][j];
                }
            }
            return dp[grid.length-1][grid[0].length-1];
        }
    }
    

    相关文章

      网友评论

          本文标题:最小路径和

          本文链接:https://www.haomeiwen.com/subject/kgnlnctx.html