AlgoPressAppearance
0062-不同路劲
https://leetcode.cn/problems/unique-paths
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？
示例 1： 
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10^9
基本思路【ME】
动态规划，dp[i,j]到达当前格子的路径可能，由上面的结果推算出来，他应该到达上方的格子的可能+到达左方的格子的可能
==注意：不能推断为左上角dp[i-1,j-1]+1，因为这样表示他只能从左上迁移过来，而实际上他可能是从上面过来，或者左边过来==
dp[i,j] = dp[i-1,j] + dp[i,j-1]
为了便于计算边界，我们可以把数组范围扩大一圈
参考代码
csharp
public class Solution {
public int UniquePaths(int m, int n) {
int[,] dp = new int[m+1,n+1];
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(i==1&&j==1){
dp[i,j] = 1;
}
else{
dp[i,j] = dp[i-1,j] + dp[i,j-1];
}
}
}
return dp[m,n];
}
}
参考代码2：数组越界处理
不扩充数组，如果是边界直接填1(i==0 或者 j==0)
csharp
public class Solution {
public int UniquePaths(int m, int n) {
int[,] dp = new int[m,n];
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i==0 || j==0){
dp[i,j] = 1;
}
else{
dp[i,j] = dp[i-1,j] + dp[i,j-1];
}
}
}
return dp[m-1,n-1];
}
}
思路2 : 官方代码，数学公式
https://leetcode.cn/problems/unique-paths/solution/bu-tong-lu-jing-by-leetcode-solution-hzjf/
从左上角到右下角的过程中，我们需要移动 m+n-2 次，其中有 m-1 次向下移动，n-1 次向右移动。因此路径的总数，就等于从 m+n-2 次移动中选择 m-1 次向下移动的方案数，即组合数： (m+n-2)! / ((m-1)!(n-1)!)
csharp
public class Solution{
public int UniquePaths(int m, int n){
long ans = 1;
for(int x = n, y = 1; y<m; x++,y++){
ans = ans * x / y;
}
return (int)ans;
}
}