当前位置：首页 > article >正文

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

article 2024/11/2 22:39:44

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