代码随想录动态规划05

74.一和零

视频讲解：动态规划之背包问题，装满这个背包最多用多少个物品？| LeetCode：474.一和零_哔哩哔哩_bilibili

代码随想录

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

• 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3

• 输出：4

• 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

  class Solution {
  public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>>dp(m+1,vector<int>(n+1,0));dp[0][0]=0;for(string &s:strs){int count0=0;int count1=0;for(char a:s){if(a=='1')  count1++;if(a=='0')  count0++;}for(int i=m;i>=count0;i--){for(int j=n;j>=count1;j--)//倒叙遍历，0-1问题{dp[i][j]=max(dp[i][j],dp[i-count0][j-count1]+1);//遍历完当前string，字符串长度应该加1}}}return dp[m][n];}
  };

  此题注意顶：1.关于字符串的遍历问题，如何遍历字符串数组中的每一个字符串的单个字符

• 2.可以效仿前面例子，计算一下sum，即count1,count0。

• 3.注意区分差异，应该使用二维数组储存

• 完全背包

  视频讲解：带你学透完全背包问题！ 和 01背包有什么差别？遍历顺序上有什么讲究？_哔哩哔哩_bilibili

  https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html 

  最大区别是每一个物体可以多次重复取

  小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。

  小明的行李箱所能承担的总重量是有限的，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。

  输入描述

  第一行包含两个整数，n，v，分别表示研究材料的种类和行李所能承担的总重量 

  接下来包含 n 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值

  #include<iostream>
  #include<vector>
  using namespace std;
  int main()
  {int n;int v;cin>>n>>v;vector<int>goods(n);//变长数组vector<int>value(n);int index1=0;int index2=0;for(int i=0;i<n;i++)
  {int wi,vi;cin>>wi>>vi;goods[index1++]=wi;value[index2++]=vi;
  }
  vector<int>dp(v+1,0);
  for(int i=0;i<n;i++)
  {for(int j=goods[i];j<=v;j++){dp[j]=max(dp[j],dp[j-goods[i]]+value[i]);}
  }
  cout<<dp[v]<<endl;
  return 0;
  }
  

  完全背包问题，for循环不用考虑倒序

  518. 零钱兑换 II

  视频讲解：动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II_哔哩哔哩_bilibili

  代码随想录

  给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

  示例 1:

  输入: amount = 5, coins = [1, 2, 5] 输出: 4

  示例 2:

  输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。

  • 5=2+2+1
  • 5=2+1+1+1
  • 5=1+1+1+1+1

  解释: 有四种方式可以凑成总金额:

  5=5

  class Solution {
  public:int change(int amount, vector<int>& coins) {vector<uint64_t>dp(amount+1,0);//防止数值相加范围超过int的边界dp[0]=1;for(int i=0;i<coins.size();i++){for(int j=coins[i];j<=amount;j++){dp[j]+=dp[j-coins[i]];}}return dp[amount];}
  };

  377. 组合总和 Ⅳ

  视频讲解：动态规划之完全背包，装满背包有几种方法？求排列数？| LeetCode：377.组合总和IV_哔哩哔哩_bilibili

  代码随想录

  给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

  题目数据保证答案符合 32 位整数范围。(注意判别是否溢出）

  class Solution {
  public:int combinationSum4(vector<int>& nums, int target) {vector<long long>dp(target+1,0);dp[0]=1;//组合个数，什么都不选for(int i=1;i<=target;i++){for(int j=0;j<nums.size();j++){if(i>=nums[j]&&(dp[i]+dp[i-nums[j]])<INT_MAX){ dp[i]+=dp[i-nums[j]];}}}
  return dp[target];}
  };

  组合DP:假设我们使用组合 DP的方式，即 先遍历硬币，再遍历金额。我们每次遍历硬币时，从小到大地更新 dp，也就是说，我们先考虑一个硬币，然后考虑如何通过已选的硬币来凑成目标金额。

  for (int num : nums) {  // 先遍历硬币for (int i = num; i <= target; i++) {  // 再遍历金额dp[i] += dp[i - num];}
  }
  

  如何理解：

  硬币 1：从金额 1 开始，遍历到目标金额 3。

  • dp[1] += dp[0]

  • dp[2] += dp[1]

  • dp[3] += dp[2]

  硬币 2：然后再考虑硬币 2，从金额 2 开始。

  • dp[2] += dp[0]

  • dp[3] += dp[1]

  • 关键点：

  • 顺序被固定：(顺序已经从小到大）
    当我们遍历硬币时，我们始终会先处理较小的硬币（比如 1），然后再考虑较大的硬币（比如 2）。在每个金额 i 上，硬币 1 会先被考虑，而硬币 2 只会在硬币 1 被处理过后再去填充 dp[i]。这种顺序确保了相同的硬币组合不会重复计算。

  • 避免重复组合：
    由于硬币的遍历顺序是固定的，我们总是从较小的硬币开始，避免了 (1, 2) 和 (2, 1) 被重复计算。因为是由小到大，所以只能是（1，2）组成，顺序已经固定

  • 换句话说，每次计算金额时，只会选择硬币之前已经考虑过的硬币，所以相同的组合只会被计入一次。

  排列DP：排列 DP： 相比之下，排列 DP 是针对 顺序不同的情况，因此我们要先遍历金额，再遍历硬币，这样每次更新时都能考虑到顺序的不同，最终统计每种排列的组合方式。

  比喻：做蛋糕

  假设你正在做一个蛋糕，你有不同种类的食材（硬币），这些食材的数量和顺序会影响蛋糕的最终味道（金额）。你的目标是做出一个指定的味道（比如 4 的蛋糕）。每次你做蛋糕时，你从不同的食材（硬币）中选择，将它们加到蛋糕中。

  步骤：

  从小到大做蛋糕： 你开始时做的是一个小蛋糕，味道是 1，然后逐渐增加味道，直到你达到 4。每次你都根据当前的蛋糕味道（当前金额），再选择一个食材（硬币）来加入。

  每次选择食材（硬币）时，都能考虑顺序： 比如你要做一个味道为 3 的蛋糕。你已经做了一个味道为 2 的蛋糕，现在你想要用食材（硬币） 1 来加，结果会变成 3，然后你继续做蛋糕。

  假设你之前已经做过味道为 2 的蛋糕，再加上食材（硬币） 1 后，你的蛋糕变成了 3，这说明你已经考虑过了食材的组合顺序，顺序是有影响的。

  70. 爬楼梯 （进阶）

  这道题目 爬楼梯之前我们做过，这次再用完全背包的思路来分析一遍

  代码随想录

  假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

  每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

  注意：给定 n 是一个正整数。

  输入描述：输入共一行，包含两个正整数，分别表示n, m

  输出描述：输出一个整数，表示爬到楼顶的方法数。

  输入示例：3 2

  输出示例：3

  提示：

  当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

  此时你有三种方法可以爬到楼顶。

  1 阶 + 1 阶 + 1 阶段 1 阶 + 2 阶  2阶+1阶

  #include <iostream>
  #include <vector>
  using namespace std;
  int main() {int n, m;while (cin >> n >> m) {vector<int> dp(n + 1, 0);dp[0] = 1;for (int i = 1; i <= n; i++) { // 遍历背包for (int j = 1; j <= m; j++) { // 遍历物品if (i - j >= 0) dp[i] += dp[i - j];}}cout << dp[n] << endl;}
  }