【LeetCode62 Unique Paths】動态規劃計算路徑

一、問題描述

給定一個m*n的方格，起始點為方格的最左上方，終點為方格的最右下方，一個機器人隻能向下以及向右移動，需要求出機器人從起始點到終點一共有多少種不重複的路徑。問題的輸入為方格的長度m以及寬度n，輸出為不同路徑的數量。

二、思路分析

這道題用動态規劃的方法非常簡單，計算出機器人從起點開始到方格内每一個格子的不同路徑數，并将路徑數量儲存到一個相同大小的m*n的矩陣中M，那麼我們隻需要輸出終點所對應的矩陣值即可。對于路徑中的每一個方格，機器人隻能經過方格上方或者方格左側進而到達方格，對應于矩陣M，我們就可以很清晰的得到M[i][j] = M[i-1][j]+M[i][j-1]，因為方格最上方以及方格最左側均隻有一條路徑到達，是以又有M[0][j] = 1以及M[i][0] = 1，其中i,j表示m,n以内的任一數字。根據這兩個公式，我們可以推斷出機器人到達每一個方格的路徑數，即可以得到完整的矩陣M值，輸出M[m-1][n-1]即可。

三、代碼實作

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