动态规划：求路径_动态规划记录路径

解法一：动态规划，时间复杂度：O(m*n) 空间复杂度：O(m*n)

不难发现，如果想到达(i,j)，需要从(i-1,j)向下移动一格或者从(i,j-1)向右移动一格，因此到大(i,j)处的走法dp[i][j]=dp[i-1][j]+dp[i][j-1]。因为到达（i,0）和（0,j）的走法都只有一种（从起点一直横着走或一直竖着走）初始化，因此初始化如下：

代码如下：

int[][] dp=new int[m][n];
for(int i=0;i<m;i++){
    dp[i][0]=0;
}
for(int j=0;j<n;j++){
    dp[0][j]=0;
}
 
for(int i=1;i<m;i++){
    for(int j=1;j<n;j++){
    dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[i-1][j-1];

解法二：组合数学 时间复杂度O(min(m,n)) 空间复杂度：O(1)

由于没有障碍物，因此从左上角到大右下角一共需要走m+n-2步，其中m-1步向下走，n-1步向右走，因此一共有

种走法=（m+n-2)!/(m-1)!*(n-1)!=(m+n-2)*...*n/(m-1)!

代码如下：

int res=1;
for(int x=n,y=1;y<m;y++,x++){
    res=res*x/y;
}
return res;