唯一路径个数从递归到迭代

标签（空格分隔）： algorithm

---

唯一路径个数

• 唯一路径个数，题目大意，给定一个的矩阵，一个机器人位于左上角的位置，目标是到达右下角的位置，从左上角到右下角的方式是，机器人所在位置，每次可以向左或者向下移动一步，问从左上角到右下角有多少条唯一的路径？

方法一：递归

• 直观想法，右下角为，那么如果到达这个位置，有两个选择，一个是从向下一步，一个是从向右一步。
• 那么假设表示从左上角到达右下角的路径数，那么依据上面分析可以得到
• 最基本情况是
• 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);
    }

• 时间复杂度:。
• 空间复杂度:函数调用

方法二：转化为备忘录递归

• 上述方式存在子问题重复计算的情况，例如计算,需要计算 ，计算的时候，还是需要计算，计算的时候也需要计算，可以发现非常多的子问题需要重新计算，我们用map，也可以用数组，来缓存已经计算完的数据。对于已经获取的数据直接返回结果。
• 对于已经计算出来的符号排列结果用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);
    }

• 时间复杂度：
• 空间复杂度：

方法三：唯一路径个数（转化为迭代计算）

• 从第二步，能看出，我们可以从基本情况（小规模的问题），来推导更为大的规模。
• 假设表示矩阵的唯一路径个数，依据上面的分析可以获得，。
• 基本情况：

    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];
    }

• 时间复杂度:
• 空间复杂度：

空间优化

• 迭代方法中可以看到每次需要使用的数据，实际上在迭代计算的时候只使用了上一行和当前行的前一个元素
• 也就是使用了和，所以我们没有必要使用所有的矩阵，只是用两行数组就可以

    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];
    }

• 时间复杂度:
• 空间复杂度：

其他

• 空间进一步优化leetcode讨论区
• cur未更新的的值就是pre的值cur[j] = cur[j] + cur[j-1]