https://leetcode-cn.com/problems/unique-paths/

Idea

因为机器人只能向下或者向右走
所以很明显 边界的路径数都是1
列出状态转移方程

就可以写出代码

PS:因为只需要保存dp[i-1][j]和 dp[i][j-1]的状态 也就是遍历了上一行之后,上上一行可以不要
空间还可以继续优化

Code

    public static int uniquePaths(int m, int n) {
        int[][] dp=new int[n][m];    //n行m列
        //机器人从 00 开始 要走到n-1 m-1 有多少种不同的路径
       for(int i=0;i<n;i++)
           dp[i][0]=1;
       for(int i=0;i<m;i++)
           dp[0][i]=1;
       for(int i=1;i<n;i++)
           for(int j=1;j<m;j++)
           {
               dp[i][j]=dp[i-1][j]+dp[i][j-1];
           }
       return dp[n-1][m-1];
    }