算法日记 32 day 动态规划（完全背包）

同样是背包问题，但01背包和完全背包是两个类型的问题。

完全背包：

完全背包与01背包的区别在于物品的个数是否是无限的。除此之外，在解决01背包的时候dp的背包遍历的顺利是倒序，为的是保证物品只被添加一次，而完全背包因为物品是无限的，所以遍历顺序也是正序。

注意：

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

我们题目来举例

题目：携带研究材料（第七期模拟笔试）

52. 携带研究材料（第七期模拟笔试） (kamacoder.com)

题目描述

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

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

输入描述

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

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

输出描述

输出一个整数，表示最大价值。

题目分析：

#include<iostream>
#include<string>
#include<vector>using namespace std;int main(){vector<int> weight;vector<int> value;int n;int v;cin>>n>>v;for(int i=0;i<n;i++){int w;int v;cin >> w >> v;weight.push_back(w);value.push_back(v);}vector<int> dp(v+1,0);for(int j = 0; j <= v; j++) { // 遍历背包容量for(int i = 0; i < weight.size(); i++) { // 遍历物品if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[v] << endl;}

题目：零钱兑换 2

518. 零钱兑换 II - 力扣（LeetCode）

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

题目分析：

一堆的物品去刚好装满一个背包，很明显的背包问题，并且是无限的，完全背包。跟着五部曲走。

dp[i][j]:从0-i的金额中任选刚好能凑出金额为J的方式数。

递推公式

背包问题都打差不差，二维数组的解法分为带I和不带I的两种方式

带i：dp[i][j]=dp[i-1][j]

不带i：dp[i][j]=dp[i][j-nums[i]]

初始化

我们可以画图分析一下就能看出来行和列的初始化值了

一维数组的优化这里就不赘述了

//二维数组
public class Solution {public int Change(int amount, int[] coins) {//dp[i][j]表示从0-i中任取能凑成j的方式int[,] dp=new int[coins.Length,amount+1];//初始化第一列for(int i=0;i<coins.Length;i++){dp[i,0]=1;}//初始化第一行for(int i=coins[0];i<=amount;i++){dp[0,i]=dp[0,i]+dp[0,i-coins[0]];//不加i和加i的和}for(int i=1;i<coins.Length;i++){//遍历物品for(int j=1;j<=amount;j++){//遍历背包if(j < coins[i]) dp[i,j] = dp[i-1,j];elsedp[i,j]=dp[i,j-coins[i]]+dp[i-1,j];}}return dp[coins.Length-1,amount];}
}//一维数组
public class Solution {public int Change(int amount, int[] coins) {//dp[i] 表示从出金额I的方式数量int[] dp=new int[amount+1];dp[0]=1;for(int i=0;i<coins.Length;i++){for(int j=coins[i];j<=amount;j++){if(j>=coins[i])dp[j]=dp[j]+dp[j-coins[i]];}}return dp[amount];}
}

题目：组合总和 4

377. 组合总和 Ⅳ - 力扣（LeetCode）

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

题目数据保证答案符合 32 位整数范围

题目分析：

这一题就是上一题的换一种问法，都一样的。直接看代码。需要注意的是，本题求得是组合数，对于背包与物品得遍历顺序有要求，先背包在物品，这一点和求排列数相反

public class Solution {public int CombinationSum4(int[] nums, int target) {int[] dp=new int[target+1];dp[0]=1;for(int j=1;j<=target;j++){for(int i=0;i<nums.Length;i++){if(j>=nums[i]){dp[j]=dp[j]+dp[j-nums[i]];}}}return dp[target];}
}

题目：爬楼梯（进阶版）

57. 爬楼梯（第八期模拟笔试） (kamacoder.com)

题目描述

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

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

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

输入描述

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

输出描述

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

题目分析：

这一次是求得排列，注意遍历顺序，这一题和之前的爬楼梯问题区别就在于每次至多上的阶梯数，如果这里的M为2其实就是爬楼梯那一题。

#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){dp[i]=dp[i]+dp[i-j];}}}cout << dp[n] << endl;}
}

题目：零钱兑换

322. 零钱兑换 - 力扣（LeetCode）

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

题目分析：

还是凑一个数，不过要求个数最少，所以在初始化的时候需要注意，初始化的值不能影响到dp的求解。

public class Solution {public int CoinChange(int[] coins, int amount) {int max=int.MaxValue/2;int[] dp=new int[amount+1];//表示凑出I的最少硬币数为dp[i]for(int i=0;i<dp.Length;i++){//初始化dp[i]=max;}dp[0]=0;for(int i=0;i<coins.Length;i++){for(int j=coins[i];j<=amount;j++){if(dp[j - coins[i]] != max){dp[j]=Math.Min(dp[j-coins[i]]+1,dp[j]);}}}if(dp[amount]==max) return -1;return dp[amount];}
}

题目：完全平方数

279. 完全平方数 - 力扣（LeetCode）

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

题目分析：

还是完全背包的问题，不过i和j都取决于同一个数n,其他部分也都差不多。和上一题一样的。

public class Solution {public int NumSquares(int n) {int max=int.MaxValue;int[] dp=new int[n+1];Array.Fill(dp,max);dp[0]=0;for(int i=1;i<=n;i++){for(int j=i*i;j<=n;j++){dp[j]=Math.Min(dp[j-i*i]+1,dp[j]);}}return dp[n];}
}

题目：单词拆分

139. 单词拆分 - 力扣（LeetCode）

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

题目分析：

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

五部曲分析：

确定dp数组以及下标的含义

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

确定递推公式

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

dp数组如何初始化

从递推公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。

public class Solution {public bool WordBreak(string s, IList<string> wordDict) {var words=new HashSet<string>(wordDict);bool[] dp=new bool[s.Length+1];dp[0]=true;for(int i=1;i<=s.Length;i++){for(int j=0;j<i;j++){if(dp[j]&&words.Contains(s.Substring(j,i-j))){dp[i]=true;break;}}}return dp[s.Length];}
}