一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為 “Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish” ）。
問總共有多少條不同的路徑？
示例 1：
輸入：m = 3, n = 7
輸出：28
示例 2：
輸入：m = 3, n = 2
輸出：3
解釋：
從左上角開始，總共有 3 條路徑可以到達右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
示例 3：
輸入：m = 7, n = 3
輸出：28
示例 4：
輸入：m = 3, n = 3
輸出：6
提示：
1 <= m, n <= 100
題目數據保證答案小于等于 2 * 109
思路
在過去，有這樣一個詞，那就是遇難則反，從起點推導出最小路徑和是困難的，那我們就從終點去推導。
解題過程
我們都知道一個方塊，只能向右或向下。在初始化dp之后，我們會有這樣一條關系式：
d p [ i ] [ j ] = { 1 if? i = = m ? 1 a n d j = = n ? 1 d p [ i + 1 ] [ j ] + d p [ i ] [ j + 1 ] if? i + 1 < m a n d j + 1 < n d p [ i + 1 ] [ j ] if? i + 1 < m d p [ i ] [ j + 1 ] if?? j + 1 < n dp[i][j] = \left\{\begin{matrix} 1 &\text{if } i == m-1 \ and \ j == n-1 \\ dp[i+1][j] + dp[i][j+1]&\text{if } i+1 < m \ and \ j+1 < n \\ dp[i+1][j]&\text{if } i+1 < m \\ dp[i][j+1] &\text{if } \ j+1 < n \end{matrix} \right. dp[i][j]=? ? ??1dp[i+1][j]+dp[i][j+1]dp[i+1][j]dp[i][j+1]?if?i==m?1?and?j==n?1if?i+1<m?and?j+1<nif?i+1<mif??j+1<n?
復雜度
時間復雜度: O ( N ? M ) O(N \cdot M) O(N?M)
空間復雜度: O ( N ? M ) O(N \cdot M) O(N?M)
Code
class Solution {
public:int uniquePaths(int m, int n) {int dp[120][120];for(int i = 1; i <= m; ++i) {for(int j = 1; j <= n; ++j) {dp[i][j] = 0;}}dp[m-1][n-1] = 1;for(int i = m-1; i >= 0; --i) {for(int j = n-1; j >= 0; --j) {if(i == m-1 && j == n-1) continue;if(i+1 < m && j+1 < n) {dp[i][j] = dp[i+1][j] + dp[i][j+1];} else {if(i+1 < m) {dp[i][j] = dp[i+1][j];}if(j+1 < n) {dp[i][j] = dp[i][j+1];}}}}return dp[0][0];}
};
)
