Leetcode 62. 不同路径 动态规划+空间优化

原题链接：Leetcode 62. 不同路径


二维数组：

class Solution {
public:int uniquePaths(int m, int n) {int res = 0;int box[m][n];for (int i = 0; i < m; i++) {box[i][0] = 1;}for (int j = 0; j < n; j++) {box[0][j] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {box[i][j] = box[i][j - 1] + box[i - 1][j];}}return box[m - 1][n - 1];}
};

空间优化，一维数组：

class Solution {
public:int uniquePaths(int m, int n) {int res = 0;int box[n];for (int j = 0; j < n; j++) {box[j] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {box[j] = box[j - 1] + box[j];}}return box[n - 1];}
};