【牛客题霸题解】求路径

一个机器人在m×n大小的地图的左上角（起点）。
机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？
首先，我们可以发现第一行和第一列的位置只能有一种方法到达

对于其它位置来说，到达这个位置有两种情况：
一种是从上面的格子走过来的
另一种是从左边的格子走过来的

所以，我们定义一个𝑚×𝑛大小的二维数组𝑑𝑝
𝑑𝑝[𝑖][𝑗]表示从起点到达第𝑖行第𝑗列的方案数。
先把第一行第一列赋值为1
然后从第二行第二列的元素开始循环
𝑑𝑝[𝑖][𝑗]=𝑑𝑝[𝑖−1][𝑗]+𝑑𝑝[𝑖][𝑗−1]
右下角的dp值就是我们要求的答案

c++

class Solution {
public:
    int uniquePaths(int m, int n) {
         int dp[110][110];
         for(int i = 1 ; i <= m ; i++){dp[i][1]=1;}//第一列赋值为1
         for(int j = 1 ; j <= n ; j++){dp[1][j]=1;}//第一行赋值为1
         for(int i = 2 ; i <= m ; i++)
         {
                 for(int j = 2 ; j <= n ; j++)
                 {
                         dp[i][j] = dp[i-1][j]+dp[i][j-1];
                 }
         }
         return dp[m][n];
    }
};

java

import java.util.*;
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++){dp[i][1]=1;}//第一列赋值为1
         for(int j = 1 ; j <= n ; j++){dp[1][j]=1;}//第一行赋值为1
         for(int i = 2 ; i <= m ; i++)
         {
                 for(int j = 2 ; j <= n ; j++)
                 {
                         dp[i][j] = dp[i-1][j]+dp[i][j-1];
                 }
         }
         return dp[m][n];
    }
}

python

class Solution:
    def uniquePaths(self , m , n ):
        dp = [[1 for i in range(n)] for j in range(m)]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

然后我们来看一种数学解法，从起点走到终点，需要向下走m-1步，向右走n-1步，总共走m+n-2步，我们从这m+n-2步中挑出n-1步向右走(或挑出m-1步向下走)，就是我们的答案了，

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long N = n + m - 2;
        long long K = n - 1;
        long long num = 1.0;
        for (int i = 1; i <= K; ++i)
        {
            num = num * (N - K + i) / i;
        }
        return (int)num;
    }
};