算法思路

一道很简单的DP问题，只要知道动态规划是什么的都不难写出状态转移方程，但是为了能够解决更难得DP问题，还是利用y总得闫氏DP分析法来进行一波严谨的分析：

状态表示：
f[i][j]表示从起点[1, 1]走到点[i, j]的所有方案的集合

属性： 走到该点的所有方案数

状态转移：
因为只能向左和向右走，所以可以右状态f[i - 1][j]和f[i][j - 1]转移过来

为了处理麻烦的边界问题，可以令下标从1开始，同时初始化，第一行每个点和每一列的方案数均为1，因为只能从起点向左或向右走得到。

C++ 代码

class Solution {
public:
    int uniquePaths(int n, int m) {
        vector<vector<int>> f(n + 1, vector<int> (m + 1, 0));

        for (int i = 1; i <= m; i ++) f[1][i] = 1;
        for (int i = 1; i <= n; i ++) f[i][1] = 1;

        for (int i = 2; i <= n; i ++)
            for (int j = 2; j <= m; j ++)
                f[i][j] += f[i - 1][j] + f[i][j - 1];

        return f[n][m];
    }
};