今天在刷leetcode的時(shí)候，遇到這樣一道題目。

大概就是說(shuō)機(jī)器人從左上角走到右下角的終點(diǎn)，每次只能向右或者向下走一步，求所有可能的唯一路徑共有多少條。最容易想到的應(yīng)該就是用DFS或者BFS將所有可能的解進(jìn)行枚舉。

typedef pair<int, int> Pos;

void dfs(Pos p, Pos end, int *count) {
    if (p.first <= end.first && p.second <= end.second) {
        if (p == end) {
            (*count)++;
        } else {
            p.first++; //向右走
            dfs(p, end, count);
            p.first--; //棧返回后恢復(fù)原來(lái)的坐標(biāo)
            p.second++; //向下走
            dfs(p, end, count);
        }
    }
}

int unique_path(int m, int n) {
    Pos begin(0, 0);
    Pos end(m - 1, n - 1);
    int count = 0;
    dfs(begin, end, &count);
    return count;
}

很遺憾，即使只是在23x12這樣的地圖上，也需要遍歷將近兩億次。那有沒有存在更優(yōu)的解呢？答案是肯定的。
我們來(lái)仔細(xì)分析下，當(dāng)機(jī)器人走到終點(diǎn)時(shí)，它的前一步要么是在1這個(gè)位置，要么就是2這個(gè)位置。

再來(lái)看當(dāng)被劃紅線的小方塊作為終點(diǎn)時(shí)，都只有一條唯一的路徑。

很明顯我們可以用動(dòng)態(tài)規(guī)劃來(lái)解決這個(gè)問題。經(jīng)過(guò)上面的分析后，可以列出狀態(tài)轉(zhuǎn)義方程：

dp[0][j] = 1
dp[i][0] = 1
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

代碼如下：

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m-1][n-1];
    }
};

相比起上面的DFS算法，使用動(dòng)態(tài)規(guī)劃時(shí)間復(fù)雜度只需要O(m*n)。在求解最優(yōu)化問題時(shí)，無(wú)非最常用的就是貪心和動(dòng)態(tài)規(guī)劃兩種。在使用動(dòng)態(tài)規(guī)劃中，先對(duì)問題仔細(xì)分析，列出狀態(tài)轉(zhuǎn)移方程以及邊界條件，接下來(lái)代碼就是水到渠成的事情了。