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

algorithm

唯一路径个数

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

方法一：递归

• 直观想法，右下角为$[m,n]$，那么如果到达这个位置，有两个选择，一个是从$[m-1,n]$向下一步，一个是从$[m,n-1]$向右一步。
• 那么假设$f(m,n)$表示从左上角到达右下角的路径数，那么依据上面分析可以得到$f(m,n) = f(m-1,n) + f(m,n-1)$
• 最基本情况是
• 1、$n=1$ 则返回$f(m,1)=1$
• 2、$m=1$ 则返回$f(1,n)=1$

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

• 时间复杂度:$T(n) = O(x^n),x \in (1,2)$。
• 空间复杂度:函数调用$O(m*n)$

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

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

• 时间复杂度：$O(m*n)$
• 空间复杂度：$O(m*n)$

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

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

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

• 时间复杂度:$O(m*n)$
• 空间复杂度：$O(m*n)$

空间优化

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

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

• 时间复杂度:$O(m*n)$
• 空间复杂度：$O(n)$

其他

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