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

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

题目

输入输出

Java代码（动态规划）

import java.util.Scanner;
public class Main{
    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(step(arr));
    }

    public static int step(int[][] arr){
        //保存结果的dp
        int[][] dp = new int[arr.length][arr[0].length];
        dp[0][0] = arr[0][0];  //存储左上角节点

        //存储第1列的值（第一列的值每个元素要想要得到最小值只能是该元素的左边和上边的元素和，左边越界了，只能是上边的）
        for(int i=1;i<arr.length;i++){
            dp[i][0] = dp[i-1][0] + arr[i][0];   //该元素的上一个元素加上这个元素的和存储dp该元素位置
        }

        //存储第1行的值（原理如上）
        for(int i=1;i<arr[0].length;i++){
            dp[0][i] = dp[0][i-1]+arr[0][i];
        }

        //存储其他结果到dp中
        for(int i=1;i<arr.length;i++){
            for(int j=1;j<arr[i].length;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + arr[i][j];
            }
        }
        //返回值
        return dp[dp.length-1][dp[0].length-1];
    }
}