算法日记 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];
else
dp[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];
}
}多重背包
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
多重背包和01背包是非常像的， 为什么和01背包像呢？
每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。
这里只做了解，不多介绍。
背包问题总结
01背包
对于二维解法，二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
对于一维解法，一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
多重背包
纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。
代码随想录 (programmercarl.com)