原题链接: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];}
};