参考题解：1

class Solution {
public:
    int uniquePaths(int m, int n) {
        int f[m][n];
        memset(f, 0, sizeof(f));
        for (int i = 0; i < m; i ++) 
            for (int j = 0; j < n; j ++)
                if (!i || !j) f[i][j] = 1;
                else f[i][j] = f[i - 1][j] + f[i][j - 1];
        return f[m - 1][n - 1];
    }   
};

未优化空间(时间O(mn), 空间O(mn)), f(m, n) 初始化为1

自己写：未优化空间, f(m, n) 初始化为1

// 自己写：未优化空间, f(m, n) 初始化为1
// f(m, n) 初始化为1 的话, f[i][0] 和 f[0][j] 不用 单独初始化为 1
class Solution {
public:
    int uniquePaths(int m, int n) {
        // if (m == 1 || n == 1) return 1; // 不用 特判
        vector<vector<int>> f(m, vector<int>(n, 1)); // 初始化为 1

        for (int i = 1; i < m; i ++ ) // i, j 下标 从 1 开始
            for (int j = 1; j < n; j ++ )
                f[i][j] = f[i - 1][j] + f[i][j - 1];

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

优化空间(时间O(mn), 空间O(n)), f(m, n) 初始化为1

自己写：采用 &1 的方式 优化空间, f(m, n) 初始化为1

// 自己写：采用 &1 的方式 优化空间, f(m, n) 初始化为1
// f(2, n) 初始化为1 的话, f[i][0] 和 f[0][j] 不用 单独初始化为 1
class Solution {
public:
    int uniquePaths(int m, int n) {
        // if (m == 1 || n == 1) return 1; // 不用 特判
        vector<vector<int>> f(2, vector<int>(n, 1)); // 初始化为 1

        for (int i = 1; i < m; i ++ ) // i, j 下标 从 1 开始
            for (int j = 1; j < n; j ++ )
                f[i & 1][j] = f[i - 1 & 1][j] + f[i & 1][j - 1];
        return f[m - 1 & 1][n - 1];
    }
};

自己写：采用 滚动数组 的方式 优化空间, f(m, n) 初始化为1

// 自己写：采用 滚动数组 的方式 优化空间, f(n) 初始化为 1
// f(n) 初始化为1 的话, f[0][j] 不用 单独初始化为 1
class Solution {
public:
    int uniquePaths(int m, int n) {
        // if (m == 1 || n == 1) return 1; // 不用 特判
        vector<int> f(n, 1); // 初始化为 1

        for (int i = 1; i < m; i ++ ) // i, j 下标 从 1 开始
            for (int j = 1; j < n; j ++ )
                f[j] = f[j] + f[j - 1];
        return f[n - 1];
    }
};

作者：有心人
链接：https://www.acwing.com/solution/content/61448/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。