唯一路徑個數(shù)從遞歸到迭代

標簽（空格分隔）： algorithm

唯一路徑個數(shù)

• 唯一路徑個數(shù)，題目大意，給定一個的矩陣，一個機器人位于左上角的位置，目標是到達右下角的位置，從左上角到右下角的方式是，機器人所在位置，每次可以向左或者向下移動一步，問從左上角到右下角有多少條唯一的路徑？

方法一：遞歸

• 直觀想法，右下角為，那么如果到達這個位置，有兩個選擇，一個是從向下一步，一個是從向右一步。
• 那么假設表示從左上角到達右下角的路徑數(shù)，那么依據(jù)上面分析可以得到
• 最基本情況是
• 1、 則返回
• 2、 則返回

    int uniquePaths(int m, int n) { return dfs(m, n); }
    int dfs(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        return dfs(m - 1, n) + dfs(m, n - 1);
    }

• 時間復雜度:。
• 空間復雜度:函數(shù)調(diào)用

方法二：轉化為備忘錄遞歸

• 上述方式存在子問題重復計算的情況，例如計算,需要計算 ，計算的時候，還是需要計算，計算的時候也需要計算，可以發(fā)現(xiàn)非常多的子問題需要重新計算，我們用map，也可以用數(shù)組，來緩存已經(jīng)計算完的數(shù)據(jù)。對于已經(jīng)獲取的數(shù)據(jù)直接返回結果。
• 對于已經(jīng)計算出來的符號排列結果用map來保存，例如map[2-3]=3，下次計算的時候可以直接使用

    unordered_map<string, int> cache;
    int uniquePaths(int m, int n) {
        return memo(m, n);
        return dfs(m, n);
    }
    int memo(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        auto key = getkey(m, n);
        if (cache.find(key) != cache.end()) {
            return cache[key];
        }
        auto x = memo(m - 1, n) + memo(m, n - 1);
        cache[key] = x;
        return x;
    }

    string getkey(int m, int n) {
        return to_string(m) + "_" + to_string(n);
    }

• 時間復雜度：
• 空間復雜度：

方法三：唯一路徑個數(shù)（轉化為迭代計算）

• 從第二步，能看出，我們可以從基本情況（小規(guī)模的問題），來推導更為大的規(guī)模。
• 假設表示矩陣的唯一路徑個數(shù)，依據(jù)上面的分析可以獲得，。
• 基本情況：

    int uniquePaths(int m, int n) {
        return dyp(m, n);
    }
    int dyp(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        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];
    }

• 時間復雜度:
• 空間復雜度：

空間優(yōu)化

• 迭代方法中可以看到每次需要使用的數(shù)據(jù)，實際上在迭代計算的時候只使用了上一行和當前行的前一個元素
• 也就是使用了和，所以我們沒有必要使用所有的矩陣，只是用兩行數(shù)組就可以

    int uniquePaths(int m, int n) {
        return dypopt(m, n);
    }
    int dypopt(int m, int n) {
        vector<int> pre(n, 1), cur(n, 1);

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j] = cur[j - 1] + pre[j];
            }
            swap(pre, cur);
        }
        return pre[n - 1];
    }

• 時間復雜度:
• 空間復雜度：

其他

• 空間進一步優(yōu)化leetcode討論區(qū)
• cur未更新的的值就是pre的值cur[j] = cur[j] + cur[j-1]