【leetcode】62 Unique Paths

发表于 | 分类于 ，


描述

在一个 m x n 的网格里，机器人位于 1 x 1 的位置，它最终要达到 m x n 的位置，每次只能向下或向右移动一格，问一共有多少种不同的走法。

样例

样例1

1
2
输入: 7 3
输出: 28

样例2

1
2
输入: 36  7
输出: 4496388

思路

  • 动态规划 dp[i][j] = dp[i-1][j] + dp[i][j-1] 注意第一行和第一列都为1
  • 直接计算，这是一个排列问题。 一共要向下走 m-1 步，向右走 n-1 步，只是考虑顺序问题，原问题转化为 (m-1)个白球 和 (n-1)个黑球排序，有多少种不同排法。这种方法要考虑溢出的问题。 计算公式为
    (m+n-2)! /((m-1)! * (n-1)!)

代码

直接计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//(m+n-2)! / ((m-1)! * (n-1)!)

class Solution {
public:
    int uniquePaths(int m, int n) {
        m--,n--;
        int bigger = m > n?m:n;
        int small = m <= n?m:n;

        long long res = 1;
        for(int i=bigger+1;i<= bigger+small;i++){
            res *= i;
        }
        // cout << res <<endl;
        long long  temp = 1;
        for(int i=1;i<=small;i++){
            temp *= i;
        }
        return res / temp;
    }
};

dp

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,1));
        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[m-1][n-1];
    }
};

参考

原题链接