一、记忆搜索

使用递归表示i,j为起点到终点的方案，因为dfs中很多重复的计算的，使用dp[i][j]记录下算好的方案数。dp[i][j]=dp[i+1][j]+dp[i][j+1]

import java.util.*;
public class Solution {
    public int[][] dp;
    public int n,m;
    public int dfs(int i,int j){
        if(i<0||i>=m||j<0||j>=n)return 0;
        if(i==m-1&&j==n-1)return dp[i][j]=1;
        if(dp[i][j]>0)return dp[i][j];
        
        dp[i][j]+=dfs(i+1,j);
        dp[i][j]+=dfs(i,j+1);
        return dp[i][j];
    }
    
    public int uniquePaths (int m, int n) {
        // write code here
        this.n = n;
        this.m = m;
        dp = new int[m][n];
        return dfs(0,0);
    }
}

组合公式

只能向下或向右走，一共走了m+n-2步，可以理解为m+n-2步中不同位置选m-1步向下，可以得到组合公式C(m+n-2,m-1)

import java.util.*;
public class Solution {
    public int uniquePaths (int m, int n) {
        // write code here
        int x = m-1;//上限
        int y = m+n-2;//下限
        long ans = 1;
        
        if(x == 0)return 1;
        for(int i = 1; i <= x;i++){
            ans = ans*(y-x+i)/i;
        }
        return (int)ans;
    }
}