# Leetcode 解題速記 62. Unique Paths
###### tags: `LeetCode` `C++`
題敘:
---
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.


Example 1:

>Input: m = 3, n = 7
>Output: 28

Example 2:

>Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
>1. Right -> Down -> Down
>2. Down -> Down -> Right
>3. Down -> Right -> Down

測資範圍:
---
* 1 <= m, n <= 100

解題筆記:
---
經典DP題之一，觀察題目可以發現，走到任何一格的方法取決於**走到該格左方**與**走到該格上方**的方法數量，因為機器人只能向右或是向下走，因此不會有走到重覆格子的問題。透過這樣的觀察可以很快得出狀態轉換方程式 : `dp[i][j] = dp[i - 1][j] + dp[i][j - 1]`

之後只要設定基底狀態，也就是`i,j`皆為0 (最上面與最右邊那排) 都為1，即可解題

程式碼:
---

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[101][101] = {0};
        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];
    }
};