求路径（动态规划）

题意

一个$m\cdot nm\backslash cdot\; n$的地图,从左上角，只能向右或向下，走到右下角，有多少种方案。

思路分析

什么叫不同的方案呢?

如果把走动的方向，变成序列，两个序列不同，则是不同的方案。

如图中

红色的走动变成序列是(向右,向右,向右,向右,向下,向下,向下)

蓝色的走动序列是(向下,向下,向下,向右,向右,向右,向右)

相邻格子的方案关系

对于从左上角走到某一个格子，那么到这个格子的上一步，一定是来自上方或者来自左方，如果来自上方，则是通过向下走到这个格子，如果是来自左方则是通过向右走到这个格子。

根据上面的序列不同则方案不同结论，这必定是不同的方案.

所以走到一个格子的方案 等于 走到它上方格子的方案 加上 走到它左方格子的方案 之和

ans[i][j] = ans[i-1][j] + ans[i][j-1]

边界处理

上面的表达式给出了递推关系，还需要处理边界

对于上边界，是i==0的情况, 所以ans[i-1][j]改为

i == 0 ? 0 : ans[i-1][j]

对于左边界，是j==0的情况，所以ans[i][j-1]改为

j == 0 ? 0 : ans[i][j-1]

初始值，是i==0 && j==0的时候，初始点的方案数是1

ans[0][0]=1

题解

最终组合上面的逻辑，最终代码

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        vector<vector<int> > ans = vector<vector<int>>(m,vector<int>(n,0));
        ans[0][0] = 1;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(i+j == 0)continue; // 初始点
                int top = i==0?0:ans[i-1][j]; // 上侧方案数
                int left = j==0?0:ans[i][j-1]; // 左侧方案数
                ans[i][j] = top + left;
            }
        }
        return ans[m-1][n-1];
    }
};

复杂度分析

时间复杂度 : 所有位置计算一次，所以总时间复杂度为$O(mn)O(mn)$

空间复杂度 : 保存了所有位置计算结果，所以总空间复杂度为$O(mn)O(mn)$

进阶(组合数)

注意到，走动方案中，向右和向下走的次数是确定的,分别为m-1和n-1.

所以相当于在m+n-2个走动中，选取n-1个位置向右，所以也可以直接使用组合数

ans = C(m+n-2,m-1)

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        long long ans = 1;
        if(n<m)swap(n,m); // make m < n
        //   (n)(n+1)...(m+n-2)   n   n+1       m+n-2
        // = ----------------- = --- ----- ... -------
        //   (1)(2)...(m-1)       1    2         m-1
        for(int i = 1;i <= m-1;i++){
            ans *= n-1+i;
            ans /= i;
        }
        return ans;
    }
};

复杂度分析

时间复杂度 : 循环次数为min(m,n),所以时间复杂度为$O(min(m,n))O(min(m,n))$

空间复杂度 : 常数个临时变量$O(1)O(1)$