您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

2021-05-25数组-中等-《矩阵的最小路径和》

题目描述

给定一个 n * m 的矩阵 a,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,输出所有的路径中最小的路径和。

示例1

输入

[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]

返回值

12

备注:

1≤n,m≤2000

1≤arri,j​≤100

思路:动态规划题目,先把边界值求出来,知道原子性的答案,再往上去求值。

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
// //         二维数组的大小
        int hang = matrix.length;//几行
        int high = matrix[0].length;//几列
        int[][] weight = new int[hang][high];
        for(int i=0;i<hang;i++){
            for(int j = 0;j<high;j++){
//                 考虑边界值
                if(i==0 && j==0)
                    weight[i][j] = matrix[0][0];
                else if(i==0){
                    weight[i][j] =  matrix[i][j] + weight[i][j-1];
                }else if(j==0){
                    weight[i][j] =  matrix[i][j] + weight[i-1][j];
                }else{//其它的
                    weight[i][j] = matrix[i][j] + Math.min(weight[i-1][j],weight[i][j-1]);
                }
            }
        }
        int sum = weight[hang-1][high-1];
        return sum;
    }
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进