题解 | 矩阵的最小路径和

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNextInt()) { 
        int n = in.nextInt();
        int m = in.nextInt();

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

        for(int i = 0;i < n;i++){
           for(int j = 0;j < m;j++){
            nums[i][j] = in.nextInt();
           }
        }

        System.out.println(run(nums,n,m));
        }
    }

    public static int run(int[][] nums,int n,int m){
        // dp[i][j] 表示从起点 (0,0) 到位置 (i,j) 的最小路径和。
        int[][] dp = new int[n + 1][m + 1];
        dp[0][0] = nums[0][0];
        // 初始化第一行
        for(int j = 1;j < m ;j++){
            dp[0][j] = dp[0][j - 1] + nums[0][j];
        }
        // 初始化第一列
        for(int i = 1;i < n ;i++){
            dp[i][0] = dp[i-1][0] + nums[i][0];
        }
        /** 到达 (i,j) 的路径只能来自上方 (i-1,j) 或左方 (i,j-1)。
        因此，dp[i][j] 的值应为这两个前驱路径的较小值加上当前格子的值： */
        for(int i = 1;i < n; i++){
            for(int j = 1;j < m;j++){
               dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + nums[i][j];
            }
        }
       return dp[n - 1][m - 1];
    }
}