LeetCode 62. Unique Paths（唯一出路Ⅰ）_地图左上角为起点,右下角为终点,计算一个人从地图起点走到终点的最小路径

题目描述：

    A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
    The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
    How many possible unique paths are there?

    Above is a 3 x 7 grid. How many possible unique paths are there?
    Note: m and n will be at most 100.

分析：
    题意：给定一个m x n 二维地图，左上角为起点，右下角为终点，一个机器人只能往下、往右走。返回到达终点所有不重复的路径条数。
    思路：这道题可以采用动态规划或者数学排列组合公式来计算。
    ① 动态规划：我们构造数组dp[m][n]，dp[i][j]表示从位置(0, 0)到达位置(i, j)的路径条数。初始化各元素值为0（其中dp[0][0] = 1，dp[i][0] = 1(i∈1→m - 1)，dp[0][j] = 1(j∈1→n - 1)），那么对于位置(i, j)，根据题意，只能从其上方或者左侧移动过来两种可能，因此状态转移方程为：
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

    时间复杂度为O(m * n)。

代码（动态规划）：

#include <bits/stdc++.h>
 
using namespace std;
 
class Solution {
public:
    int uniquePaths(int m, int n) {
        // Exceptional Case: 
		if(m <= 0 || n <= 0){
			return 0;
		}
		// create
		vector<vector<int>> dp(m, vector<int>(n, 0));
		// init
		dp[0][0] = 1;
		for(int i = 1; i <= n - 1; i++){
			dp[0][i] = 1;
		}
		for(int i = 1; i <= m - 1; i++){
			dp[i][0] = 1;
		}
		// dp
		for(int i = 1; i <= m - 1; i++){
			for(int j = 1; j <= n - 1; j++){
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
		// get answer
		return dp[m - 1][n - 1];
    }
};

    ② 数学：这道题总共需要向右移动(n - 1)步、向下(m - 1)步，等价于从(m - 1) + (n - 1) = (m + n - 2)步中，选择(m - 1)步向下走（等价于选择(n - 1)步向右走）。因此，这道题的本质是计算排列数C(m + n - 2, m - 1)。

代码（数学）：

#include <bits/stdc++.h>
 
using namespace std;
 
// C(m + n - 2, m - 1)
class Solution {
public:
    int uniquePaths(int m, int n) {
        if((m <= 0) || (n <= 0)){
            return 0;
        }
        double ans = 1.0;
        for(int i = 1; i <= m - 1; i++){
            ans = ans * (n + i - 1) / i;
        }
        return (int)ans;
    }
};