美文网首页
每日一题:64. 最小路径和

每日一题:64. 最小路径和

作者: 北漂三十年 | 来源:发表于2023-03-09 17:49 被阅读0次

package com.ljp.test.leetcode;

/**

* <b>64. 最小路径和

*

*

* 给定一个包含非负整数的 mxn 网格grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

*

* 说明:每次只能向下或者向右移动一步。

*

*

* 示例 1:

*

*

* 输入:grid = [[1,3,1],[1,5,1],[4,2,1]]

* 输出:7

* 解释:因为路径 1→3→1→1→1 的总和最小。

* 示例 2:

*

* 输入:grid = [[1,2,3],[4,5,6]]

* 输出:12

*

* 提示:

*

* m == grid.length

* n == grid[i].length

* 1 <= m, n <= 200

* 0 <= grid[i][j] <= 100

*

* 来源:力扣(LeetCode)

* 链接:<a href="https://leetcode.cn/problems/minimum-path-sum">64. 最小路径和

* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

*

* @author luojunping

* @since 2023-03-09

*/

public class Number0064{

    public static void main(String[] args) {

        int[][] nums1 ={{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};

        int[][] nums2 ={{1, 2, 3}, {4, 5, 6}};

        System.out.println(DynamicPlanning.minPathSum(nums1));

        System.out.println(DynamicPlanning.minPathSum(nums2));

    }

    /**

    * 动态规划

    */

    private static class DynamicPlanning{

        public static int minPathSum(int[][] nums) {

            int m = nums.length;

            int n = nums[0].length;

            int[][] dp =new int[m][n];

            dp[0][0] = nums[0][0];

            for (int i =1; i < m; i++) {

                dp[i][0] = dp[i -1][0] + nums[i][0];

            }

            for (int i =1; i < n; i++) {

                dp[0][i] = dp[0][i -1] + nums[0][i];

            }

            for (int i =1; i < m; i++) {

                for (int j =1; j < n; j++) {

                    int minimum = Math.min(dp[i -1][j], dp[i][j -1]);

                    dp[i][j] = minimum + nums[i][j];

                }

            }

            return dp[m -1][n -1];

        }

    }

}

相关文章

网友评论

      本文标题:每日一题:64. 最小路径和

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