菜鸡第一次自己思考用动态规划的思想解决的问题

菜鸡第一次独立思考解决掉的问题。。。
目前我对动态规划的理解，很多时候需要借助一个额外的存储空间（记忆空间）来解决，和刚开始学编程用一个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));
    }
}