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

代码随想录动态规划05

article 2025/4/1 0:33:20

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