不同路径

leetcode.cn/problems/unique-paths/" rel="nofollow">不同路径

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];}
};

leetcode.cn/problems/unique-paths-ii/" rel="nofollow">不同路径 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];}
};

leetcode.cn/problems/unique-paths-iii/" rel="nofollow">不同路径 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;}}}
};

组合总和

leetcode.cn/problems/combination-sum/" rel="nofollow">组合总和 【无重复数字+无限制选择次数】

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();}}
};

leetcode.cn/problems/combination-sum-ii/" rel="nofollow">组合总和 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();}}
};

leetcode.cn/problems/combination-sum-iii/" rel="nofollow">组合总和 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) == xSumif (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;}
};

leetcode.cn/problems/combination-sum-iv/" rel="nofollow">组合总和 Ⅳ【无重复数字+爬楼梯】

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];}
};

最大连续 1 的个数

leetcode.cn/problems/max-consecutive-ones/" rel="nofollow">最大连续 1 的个数【无翻转】

class Solution {
public:int findMaxConsecutiveOnes(vector<int>& nums) {int maxCount = 0, count = 0;int n = nums.size();for (int i = 0; i < n; i++) {if (nums[i] == 1) {count++;} else {maxCount = max(maxCount, count);count = 0;}}maxCount = max(maxCount, count);return maxCount;}
};

leetcode.cn/problems/max-consecutive-ones-ii/" rel="nofollow">最大连续1的个数 II

class Solution {
public:int findMaxConsecutiveOnes(vector<int>& nums, int k = 1) {int ret = 0;int left = 0, zeroNum = 0;for (int right = 0; right < nums.size(); right++) {if (nums[right] == 0)zeroNum++;while (zeroNum > k) // 理解这里的while的必要性【if不错但不好】{if (nums[left] == 0)zeroNum--;left++;}ret = max(ret, right - left + 1);}return ret;}
};

leetcode.cn/problems/max-consecutive-ones-iii/" rel="nofollow">最大连续1的个数 III【翻转K个零】

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int ret = 0;int left = 0, zeroNum = 0;for (int right = 0; right < nums.size(); right++) {if (nums[right] == 0)zeroNum++;while (zeroNum > k) // 理解这里的while的必要性【if不错但不好】{if (nums[left] == 0)zeroNum--;left++;}ret = max(ret, right - left + 1);}return ret;}
};

我不想上课【连续0的个数+翻转k个1】

#include <algorithm>
#include <iostream>
#include <vector>using namespace std;int longestOnes(vector<int>& nums, int k) {int ret = 0;int left = 0, oneNum = 0;for (int right = 0; right < nums.size(); right++) {if (nums[right] == 1)oneNum++;while (oneNum > k) {if (nums[left] == 1)oneNum--;left++;}ret = max(ret, right - left + 1);}return ret;
}
int main() {vector<int> days(31);for (int i = 0; i < 31; ++i) {cin >> days[i]; // 输入 31 天的课程情况}cout << longestOnes(days, 1) << endl;return 0;
}

打家劫舍

1.打家劫舍【线性房屋】

198. 打家劫舍 - 力扣（LeetCode）

1.0递归+记忆化搜索

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();vector<int> cache(n, -1);return robRecursive(n - 1, nums, cache);}int robRecursive(int i, vector<int>& nums, vector<int>& cache) {if (i < 0)return 0;if (cache[i] != -1)return cache[i];return cache[i] = max(robRecursive(i - 1, nums, cache),robRecursive(i - 2, nums, cache) + nums[i]);return cache[i];}
};

1.1一维数组

class Solution
{
public:int rob(vector<int> &nums){int n = nums.size();if (n == 0)return 0;// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额vector<int> dp(n, 0);dp[0] = nums[0];if (n == 1)return dp[0];dp[1] = max(nums[0], nums[1]);if (n == 2)return dp[1];for (int k = 2; k <= n - 1; k++){dp[k] = max(dp[k - 1], nums[k] + dp[k - 2]);}return dp[n - 1];}
};

1.2三变量法

class Solution
{
public:int rob(vector<int> &nums){int n = nums.size();if (n == 0)return 0;int prv = nums[0]; // dp[0]if (n == 1)return prv;int cur = max(nums[0], nums[1]); // dp[1]if (n == 2)return cur;// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额for (int i = 2; i < n; i++){// dp[k] = max(dp[k - 1], nums[k] + dp[k - 2]);int tmp = max(cur, nums[i] + prv);prv = cur;cur = tmp;}return cur;}
};

1.2三变量法【高手】【推荐】

class Solution {
public:int rob(vector<int>& nums) {int f0 = 0, f1 = 0;for (int x : nums) {int new_f = max(f1, f0 + x);f0 = f1;f1 = new_f;}return f1;}
};

1.3双数组法

class Solution
{
public:int massage(vector<int> &nums){int n = nums.size();if (n == 0)return 0;// f[i] 走到i时 偷nums[i]// g[i] 走到i时 不偷nums[i]vector<int> f(n);vector<int> g(n); // auto g = f;f[0] = nums[0];for (int i = 1; i < n; i++){f[i] = nums[i] + g[i - 1];g[i] = max(f[i - 1], g[i - 1]);}return max(f[n - 1], g[n - 1]);}
};

2.打家劫舍2【环形房屋】

打家劫舍2

2.1双数组法

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));}int rob1(vector<int>& nums, int left, int right) {if (left > right)return 0;int n = nums.size();vector<int> f(n);auto g = f;f[left] = nums[left];for (int i = left + 1; i <= right; i++) {f[i] = g[i - 1] + nums[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[right], g[right]);}
};

2.2 三变量法【新手】

class Solution
{
public:int robRange(vector<int> &nums, int start, int end){int n = end - start + 1;if (n == 0)return 0;int prv = nums[start]; // dp[k-2]if (n == 1)return prv;int cur = max(nums[start], nums[start + 1]); // dp[k-1]if (n == 2)return cur;for (int i = start + 2; i <= end; i++){// dp[k] = max(dp[k - 1], nums[k - 1] + dp[k - 2]);int tmp = max(cur, nums[i] + prv);prv = cur;cur = tmp;}return cur;}int rob(vector<int> &nums){int n = nums.size();if (n == 1)return nums[0];else if (n == 2)return max(nums[0], nums[1]);else if (n == 3)return max(max(nums[0], nums[1]), nums[2]);// 偷nums[0]不能偷nums[1]和nums[n-1] 能偷[2, n - 2]// 不偷nums[0] 能偷[1, n - 1]return max(nums[0] + robRange(nums, 2, n - 2), robRange(nums, 1, n - 1));}
};

2.2 三变量法【高手】【推荐※】

class Solution {int rob1(vector<int>& nums, int start, int end) {int f0 = 0, f1 = 0;for (int i = start; i <= end; i++) {int new_f = max(f1, f0 + nums[i]);f0 = f1;f1 = new_f;}return f1;}public:int rob(vector<int>& nums) {int n = nums.size();return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));}
};

3.打家劫舍3【树形DP】

高手思路

class Solution {pair<int, int> dfs(TreeNode* node) {if (node == nullptr) { // 递归边界return {0, 0};     // 没有节点，怎么选都是 0}auto [l_rob, l_not_rob] = dfs(node->left);   // 递归左子树auto [r_rob, r_not_rob] = dfs(node->right);  // 递归右子树int rob = l_not_rob + r_not_rob + node->val; // 选int not_rob = max(l_rob, l_not_rob) + max(r_rob, r_not_rob); // 不选return {rob, not_rob};}public:int rob(TreeNode* root) {auto [root_rob, root_not_rob] = dfs(root);return max(root_rob, root_not_rob); // 根节点选或不选的最大值}
};

4.删除相邻数字的最大分数

删除相邻数字的最大分数_牛客题霸_牛客网 (nowcoder.com)

1. 一个数组选了x可以得x分 但是值为x-1和x+1的数将会消失 直到数字全被消失或选择 问最高分数
2. 遍历数组arr 填充hash arr中的per在hash中作下标 表示 【谁 出现的总和】如4在arr中出现了2次 则hash[4]=8
3. 由此问题转变为 在hash中 我“偷”了某个下标i 获得了hash[i]分数 与i相邻的就不能偷了

4.1双状态数组

#include <iostream>
#include <vector>
using namespace std;int main()
{const int N = 1e4 + 10;int hash[N] = {0};int n = 0;cin >> n;int per = 0;int end = 0;for (int i = 0; i < n; i++){cin >> per;end = per > end ? per : end;hash[per] += per;}vector<int> f(end + 1, 0);vector<int> g(end + 1, 0);for (int i = 1; i <= end; i++){f[i] = g[i - 1] + hash[i];g[i] = max(f[i - 1], g[i - 1]);}cout << max(f[end], g[end]) << endl;return 0;
}

4.2一维数组

#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0;cin >> n;int per = 0;int end = 0;const int N = 1e4 + 10;int hash[N] = {0};for (int i = 0; i < n; i++){cin >> per;end = per > end ? per : end;hash[per] += per;}vector<int> dp(end + 1, 0);// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额dp[0] = hash[0];dp[1] = max(hash[0], hash[1]);for (int k = 2; k <= end; k++){dp[k] = max(dp[k - 1], hash[k] + dp[k - 2]);}cout << dp[end] << endl;return 0;
}

4.3三变量法

#include <iostream>
#include <vector>
using namespace std;int main()
{const int N = 1e4 + 10;int hash[N] = {0};int n = 0;cin >> n;int per = 0;int end = 0;for (int i = 0; i < n; i++){cin >> per;end = per > end ? per : end;hash[per] += per;}// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额int prv = hash[0];               // dp[0]int cur = max(hash[0], hash[1]); // dp[1]for (int i = 2; i <= end; i++){// dp[k] = max(dp[k - 1], hash[k] + dp[k - 2]);int tmp = max(cur, hash[i] + prv);prv = cur;cur = tmp;}cout << cur << endl;return 0;
}

leetcode.cn/problems/house-robber-iv/" rel="nofollow">打家劫舍 IV【最小化最大值问题】