leetcode筆記：Unique Paths

一. 題目描述

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?<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPk5vdGU6IG0gYW5kIG4gd2lsbCBiZSBhdCBtb3N0IDEwMC48L3A+DQo8cD48c3Ryb25nPrb+LiDM4sS/t9bO9jwvc3Ryb25nPjwvcD4NCjxwPszixL+1xLTz0uLKx7v6xvfIy9Ta0ru49r7Y1fPA79ffwrejrLnmtqjG8LXjoaLW1bXjus3X38K3tcS3vc/yo6zOytffzerIq7PM19y5stPQvLjW1tfft6iho7jDzOLK18/Iz+u1vdPDye62yNPFz8jL0cv3wLTX9qOstavKx73hufvKx7OsyrGho7/JyrnTw7avzKy55ruuwLTX9qOsyejXtMyszqo8Y29kZT5rW2ldW2pdPC9jb2RlPqOsse3KvrTTxvC14zxjb2RlPigwLCAwKTwvY29kZT61vbTvPGNvZGU+KGksIGopPC9jb2RlPrXEwrfP38z1yv2jrNTy17TMrNeq0sa3vbPMzqqjujwvcD4NCjxwcmUgY2xhc3M9"brush:java;"> k[i][j]=k[i-1][j]+k[i][j-1]

使用動態規劃時，需注意邊界條件的設定。

以下代碼使用new創建一維數組（數組大小為m * n）並將其作為二維數組使用，第i行、j列的元素可表示為：k[i * n + j] ，這樣創建二維數組的好處是內存連續，但表示不夠直觀。

三. 示例代碼

#include 

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個時間點向右走的方法有多少種，公式：