题解 | 矩阵的最小路径和

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int[][] nums = new int[a][b];
        // 注意 hasNext 和 hasNextLine 的区别
        for(int i = 0; i < a; i++) { // 注意 while 处理多个 case
            for(int j = 0; j < b; j++){
                nums[i][j] = in.nextInt();
            }
        }
        int[][] dp = new int[a][b];
        dp[0][0] = nums[0][0];
	  	// 初始化dp，第一行和第一列的值都是固定的
        for(int i = 1; i < b; i++){
            dp[0][i] = nums[0][i] + dp[0][i - 1];
        }
        for(int i = 1; i < a; i++){
            dp[i][0] = nums[i][0] + dp[i - 1][0];
        }
        // printDP(dp);
        // 不需要考虑边界
	  	// 计算出每个位置的最小路径和
        for(int i = 1; i < a; i++){
            for(int j = 1; j < b; j++){
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + nums[i][j];
            }
        }
        // printDP(dp);
        System.out.println(dp[a - 1][b - 1]);
    }

    public static void printDP(int[][] dp){
        for(int i = 0; i < dp.length; i++){
            for(int j = 0; j < dp[0].length; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }
}