【力扣-递归/搜索/回溯/动态规划】不同路径+组合总和{题解分享}

不同路径

不同路径

class Solution {
    int dfs(int i, int j, vector<vector<int>>& memo) {
        if (memo[i][j] != 0)
            return memo[i][j];

        if (i == 0 || j == 0)
            return 0;
        if (i == 1 && j == 1)
            return memo[i][j] = 1;

        memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
        return memo[i][j];
    }

public:
    int uniquePaths(int m, int n) {
        // 解法一：数学/组合数
        // long long ans = 1;
        // // 第一次y=1 最后一次y=m-1
        // // 第一次x=n 最后一次x=n+m-2
        // for (int x = n, y = 1; y < m; ++x, ++y) {
        //     ans = ans * x / y;
        // }
        // return ans;

        // 解法二: 记忆化搜索
        vector<vector<int>> memo(m + 1, vector<int>(n + 1));
        return dfs(m, n, memo);

        // 解法三：动态规划
        // vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        // dp[1][1] = 1;
        // for (int i = 1; i <= m; i++)
        //     for (int j = 1; j <= n; j++) {
        //         if (i == 1 && j == 1)
        //             continue;
        //         dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        //     }
        // return dp[m][n];
    }
};

不同路径 II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) {
        int m = ob.size(), n = ob[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (ob[i - 1][j - 1] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m][n];
    }
};

不同路径 III

class Solution {
    bool vis[21][21];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int ret;
    int m, n, step;

public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        int bx = 0, by = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 0)
                    step++;
                else if (grid[i][j] == 1) {
                    bx = i;
                    by = j;
                }
        step += 2;
        vis[bx][by] = true;
        dfs(grid, bx, by, 1);
        return ret;
    }
    void dfs(vector<vector<int>>& grid, int i, int j, int count) {
        if (grid[i][j] == 2) {
            if (count == step) // 判断是否合法
                ret++;
            return;
        }
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&
                grid[x][y] != -1) {
                vis[x][y] = true;
                dfs(grid, x, y, count + 1);
                vis[x][y] = false;
            }
        }
    }
};

组合总和

组合总和 【无重复数字+无限制选择次数】

class Solution {
    int aim;
    vector<int> path;
    vector<vector<int>> ret;

public:
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        aim = target;
        dfs(nums, 0, 0);
        return ret;
    }
    void dfss(vector<int>& nums, int pos, int sum) {
        if (sum == aim) {
            ret.push_back(path);
            return;
        }
        if (sum > aim || pos == nums.size())
            return;

        for (int i = pos; i < nums.size(); i++) {
            path.push_back(nums[i]);
            dfss(nums, i, sum + nums[i]);
            path.pop_back();
        }
    }
    void dfs(vector<int>& nums, int pos, int sum) {
        if (sum == aim) {
            ret.push_back(path);
            return;
        }
        if (sum > aim || pos == nums.size())
            return;

        for (int k = 0; k * nums[pos] + sum <= aim; k++) {
            if (k != 0)
                path.push_back(nums[pos]);
            dfs(nums, pos + 1, sum + k * nums[pos]);
        }

        for (int k = 1; k * nums[pos] + sum <= aim; k++) {
            path.pop_back();
        }
    }
};

组合总和 II 【有重复数字+只能选择一次】

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
    int n;
    int aim;

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        ranges::sort(candidates);
        n = candidates.size();
        aim = target;
        dfs(candidates, 0, 0);
        return ans;
    }
    void dfs(vector<int>& candidates, int pos, int sum) {
        if (sum == aim) {
            ans.push_back(path);
            return;
        }

        if (sum > aim || pos == n)
            return;

        for (int i = pos; i < n; i++) {
            if (i > pos && candidates[i] == candidates[i - 1])
                continue;

            path.push_back(candidates[i]);
            dfs(candidates, i + 1, sum + candidates[i]);
            path.pop_back();
        }
    }
};

组合总和 III【「在 9 个数中选择 k 个数」的组合枚举】

class Solution {
    vector<int> path;
    vector<vector<int>> ans;

    int x;
    int xSum;

public:
    void dfs(int cur, int n, int pathSum) {
        if (path.size() + (n - cur + 1) < x || path.size() > x)
            return;

        // accumulate(path.begin(), path.end(), 0) == xSum
        if (path.size() == x && pathSum == xSum) {
            ans.push_back(path);
            return;
        }
        path.push_back(cur);
        dfs(cur + 1, n, cur + pathSum);
        path.pop_back();

        dfs(cur + 1, n, pathSum);
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        x = k;
        xSum = n;
        int pathSum = 0;
        dfs(1, 9, pathSum);
        return ans;
    }
};

组合总和 Ⅳ【无重复数字+爬楼梯】

class Solution {
    // dfs(i) 表示爬 i 个台阶的方案数
    int dfs(int i, vector<int>& nums, vector<int>& memo) {
        if (i == 0)
            return 1;

        int& res = memo[i]; // 注意这里是引用
        if (res != -1)
            return res;

        res = 0;
        for (int x : nums) {
            if (x <= i) {
                res += dfs(i - x, nums, memo);
            }
        }
        return res;
    }

public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> memo(target + 1, -1);
        // return dfs(target, nums, memo);

        vector<unsigned> f(target + 1);
        f[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int x : nums) {
                if (x <= i)
                    f[i] += f[i - x];
            }
        }
        return f[target];
    }
};

原文地址：https://blog.csdn.net/LHRan_ran_/article/details/145239112

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！