矩阵的最小路径和

[编程题]矩阵的最小路径和

热度指数：10392 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

第一行输入两个整数 n 和 m，表示矩阵的大小。

接下来 n 行每行 m 个整数表示矩阵。

输出描述:

输出一个整数表示答案。

示例1

输入

输出

备注:

算法知识视频讲解

Java

pein531

动态规划模版题，上边界只能从左边转移过来，左边界只能从上边转移过来，其他位置从上边和左边中选择代价小的方式转移过来。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
        int[][] grid = new int[n][m];
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            for(int j = 0; j < m; j++)
                grid[i][j] = Integer.parseInt(params[j]);
        }
        for(int i = 1; i < m; i++) grid[0][i] += grid[0][i - 1];
        for(int i = 1; i < n; i++) grid[i][0] += grid[i - 1][0];
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++)
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        }
        System.out.println(grid[n - 1][m - 1]);
    }
}

发表于 2021-11-21 19:53:30 回复(0)

Java

泠月sama

基于动态规划思想，使用了dp[i][j]存储：到第i行，j列最短路径。遍历完毕后，最后直接输出到右下角点的最短路径就可以。

import java.util.*;
public class Main1{
    
    static int findMin(int[][] path,int row,int col) {
        if(row<1||col<1)
            return -1;
        else if(row==1&&col==1)
            return path[0][0];
        else if(row==1) {
            int min=0;
            for(int i=0;i<col;i++) {
                min+=path[0][i];
            }
            return min;
        }
        else if(col==1) {
            int min=0;
            for(int i=0;i<row;i++) {
                min+=path[i][0];
            }
            return min;
        }
        int[][] dp=new int[row][col];
        dp[0][0]=path[0][0];
        for(int i=1;i<row;i++) {
            dp[i][0]=dp[i-1][0]+path[i][0];
        }
        for(int i=1;i<col;i++) {
            dp[0][i]=dp[0][i-1]+path[0][i];
        }
        
        for(int i=1;i<row;i++) {
            for(int j=1;j<col;j++) {
                dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+path[i][j];
            }
        }
        return dp[row-1][col-1];
    }
    
    public static void main(String[] args){
        int row;int col;
        Scanner in=new Scanner(System.in);

        while(in.hasNext()){
            row=in.nextInt();
            col=in.nextInt();
            int[][] path=new int[row][col];
            for(int i=0;i<row;i++) {
                for(int j=0;j<col;j++) {
                    path[i][j]=in.nextInt();
                }
            }
            System.out.println(findMin(path,row,col));
        }
    }
}

发表于 2020-04-23 17:43:59 回复(0)

Java

牛客197105342号

菜鸡第一次独立思考解决掉的问题。。。

目前我对动态规划的理解，很多时候需要借助一个额外的存储空间（记忆空间）来解决，和刚开始学编程用一个flag变量来记录状态一样。

问题既然是求到最后一个位置的最小值，那么最后一个位置的值是怎么来的呢？按照动态规划的思想，必然是来自前一个记录位置的较小值加上最后一个位置的值，肯定是最小的，以此回推。由于移动的方向只能是向右和向下，最后一个位置最小，必然是从它的左边或者正上方那个较小的值而来。
按照这种思路，第一个位置时，就是它本身。第一行都是是向右所得，第一列都是向下移动所得，从第2行和第2列开始，这里先求出来，直接从第2行和第2列开始，直到最后一个位置。这里求出第1行和第1列的值我也是为了最后循环方便

这里是自顶向下，我也知道最好是从自底向上，但是先这样，慢慢养成思维习惯！！加油！！！

代码

import java.util.Scanner;
public class Main{
    public static int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];      //起点位置
        //求第1列的值
        for(int i = 1;i<grid.length;i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        //求第1行的值
        for(int i = 1;i<grid[0].length;i++){
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        //循环结束，最后的结果即为最小值
        for(int i = 1;i<grid.length;i++){
            for(int j = 1;j<grid[0].length;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }

        return dp[grid.length-1][grid[0].length-1];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j = 0;j<m;j++){
                arr[i][j] = sc.nextInt();
            }
        }
        System.out.println(minPathSum(arr));
    }
}

发表于 2020-04-14 17:01:18 回复(0)