**一. 題目描述** A robot is located at the top-left corner of a m  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 * 7 grid. How many possible unique paths are there? Note: m and n will be at most 100. **二. 題目分析** 題目的大意是機器人在一個矩陣里走路，規定起點、終點和走路的方向，問走完全程總共有幾種走法。該題首先想到用深度優先搜索來做，但是結果是超時。可使用動態規劃來做，設狀態為`k[i][j]`，表示從起點`(0, 0)`到達`(i, j)`的路線條數，則狀態轉移方程為： ~~~ k[i][j]=k[i-1][j]+k[i][j-1] ~~~ 使用動態規劃時，需注意邊界條件的設定。 以下代碼使用new創建一維數組（數組大小為`m * n`）并將其作為二維數組使用，第`i`行、`j`列的元素可表示為：`k[i * n + j]`?，這樣創建二維數組的好處是內存連續，但表示不夠直觀。 **三. 示例代碼** ~~~ #include <iostream> using namespace std; class Solution { public: // 深搜，會超時 int uniquePaths(int m, int n) { if (m <= 0 || n <= 0) return 0; if (m == 1 || n == 1) return 1; return uniquePaths(m - 1, n) + uniquePaths(m, n - 1); } // 動態規劃 int uniquePaths2(int m, int n) // 動態規劃 { int *k = new int[m * n]; // 到兩條邊處各點的走法只有一種 for (int i = 0; i < m; ++i) k[i * n] = 1; for (int j = 0; j < n; ++j) k[j] = 1; for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { k[i * n + j] = k[(i - 1) * n + j] + k[i * n + j - 1]; } } int result = k[(m - 1) * n + n - 1]; delete [] k; return result; } }; ~~~  **四. 小結** 事實上，如果只是求出路線的種數，完全可以將該問題轉化為數學問題。假設一個`m`行`n`列的矩陣，機器人從左上走到右下總共需要的步數是`m + n - 2`，其中向下走的步數是`m - 1`，因此問題變成了在`m + n - 2`個操作中，選擇`m – 1`個時間點向下走，選擇方式有多少種，可用以下公式算出：  若考慮向右走的情況，則步數為`n - 1`，問題也可解釋為在`m + n - 2`個操作中，選擇`n – 1`個時間點向右走的方法有多少種，公式：