• 最小路径和


    1 题目描述
    给出一个包含非负整数的m×n矩阵,从左上角出发至右下角,每次只能向右或者向下移动一步,找出数字之和最小的路径。
    输入:matrix = [[1,2,7],[2,5,3],[1,1,1]],如图2-3所示。
    1  2  7
    2  5  3
    1  1  1
    输出:6。
    解释:路径1→2→1→1→1的总和最小。
    2 题目解析
    (1)定义问题状态:定义一个m×n二维数组dp[][],dp[i][j]代表从左上角出发到(i,j)位置的最小路径和。
    (2)定义初始条件:dp[0][0] = matrix [0][0]。
    (3)确定转移方程:根据题意,每次只能向右或者向下移动一步,可确定状态转移方程:
    ● 当j = 0时,dp[i][0] = dp[i-1][0] + matrix[i][0]。
    ● 当i = 0时,dp[0][j] = dp[0][j-1] + matrix[0][j]。
    ● 当i > 0 且 j > 0时,dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]。
    最终,dp[m-1][n-1]就是待求结果。
    3、代码实现
    1. public class MinPathSum {
    2. public static void main(String[] args) {
    3. int[][] matrix = {{1, 2, 7}, {2, 5, 3}, {1, 1, 1}};
    4. System.out.println(minPathSum(matrix));
    5. }
    6. public static int minPathSum(int[][] matrix) {
    7. int row = matrix.length; // 行数
    8. int col = matrix[0].length; // 列数
    9. int[][] dp = new int[row][col];
    10. dp[0][0] = matrix[0][0];
    11. // 先初始化dp第一行
    12. for (int i = 1; i < row; i++) {
    13. dp[i][0] = matrix[i][0] + dp[i - 1][0];
    14. }
    15. // 初始化dp第一列
    16. for (int j = 1; j < col; j++) {
    17. dp[0][j] = matrix[0][j] + dp[0][j - 1];
    18. }
    19. // 计算dp[i][j],i和j从1开始
    20. for (int i = 1; i < row; i++) {
    21. for (int j = 1; j < col; j++) {
    22. dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j], dp[i][j -1]);
    23. }
    24. }
    25. return dp[row - 1][col - 1];
    26. }
    27. }

  • 相关阅读:
    前端菜鸟浅谈Web前端开发技术
    处理机调度
    怎样写出好文章?
    JavaScript:DOM
    lambda表达式,函数式接口和方法引用
    生成器高级用法
    Python判断对象是否包含对应的属性hasattr()
    判断链表是否是环形链表
    如何在interface中处理DUT中的inout信号
    redis高可用
  • 原文地址:https://blog.csdn.net/Baoge_leopard/article/details/138189045