！！！题解 | 不同路径的数目(一) 注意这个问题也有重复的计算，所以还是可以用DP数组去优化

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // 定义dp数组
        int[][] dp = new int[m][n];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                // 当 i = 0：dp[0][j] = dp[0][j-1]
                if(i == 0){
                    dp[i][j] = 1; // 都是1是因为dp[0][j] = dp[0][j-1]，所以干脆全部赋值为1
                    continue;
                }
                // 当 j = 0：dp[i][0] = dp[i-1][0]
                if(j == 0){
                    dp[i][j] = 1;
                    continue;
                }
                // 当 i > 1 && j > 1 :  dp[i][j] = dp[i][j-1] + dp[i-1][j]
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1]; // 返回到达终点的所有可行路径
    }
}