动态规划（一）：组合型DP之背包问题一（含记忆化搜索版）
动态规划：空间换时间
两种实现方式
1.迭代法：自底向上方法的递推法
2.记忆化搜索：带备忘的自顶向下发的递归回溯法
1.AcWing2.01背包问题
01背包求最大价值
一：迭代法
1.状态表示：f[i][j]：在背包有j的体积可用的情况下，考虑在前i个物品中选择物品，存下所有选择情况中能获得的最大价值
2.状态转移方程：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);//01背包:选or不选
3.初值：f[0][i]都等于0
二：记忆化搜索
1.记忆化数组状态表示:mem[k][V]:在背包有v的体积可用的情况下，考虑第k个物品到最后一个物品中做选择，
存下所有选择情况下获得的价值中的最大值
2.递归搜索（状态转移）：
不选：x=dfs(k+1,V);
选：if(v[k]<=V)y=dfs(k+1,V-v[k])+w[k];//能选
else y=dfs(k+1,V);//不能选
mem[k][V]=max(x,y);//记忆化
3.记忆数组初始化：mem[i][j]全为-1，表示起始各个情况都没出现过
4.记忆条件：mem[k][V]>=0，表示以前这个情况出现过，直接返回以前的值
5.边界条件（初值）：if(k==n+1)return 0;//无物品可选，获得的价值最大为0
2.AcWing 3.完全背包问题
完全背包求最大价值
一：迭代法
1.状态表示：f[i][j]：在背包有j的体积可用的情况下，考虑在前i个物品中选择物品，存下所有选择情况中能获得的最大价值
2.朴素版状态转移方程：f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);（多一层循环枚举k，会超时）
3.优化版状态转移方程：f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);（省略了一些重复计算部分）
4.初值：f[0][i]都等于0
二：记忆化搜索
1.记忆化数组状态表示:mem[k][V]:在背包有v的体积可用的情况下，考虑第k个物品到最后一个物品中做选择，
存下所有选择情况下获得的价值中的最大值
2.朴素版递归搜索（状态转移）（多一层循环枚举k，会超时）：
for(int i=0;v[k]*i<=V;i++)//第k个物品选i次
mem[k][V]=max(res,dfs(k+1,V-v[k]*i)+i*w[k]);
3.优化版递归搜索（状态转移）（省略了一些重复计算部分）：
if(V>=v[k])mem[k][V]=max(dfs(k,V-v[k])+w[k],dfs(k+1,V));
else mem[k][V]=dfs(k+1,V);
4.记忆数组初始化：mem[i][j]全为-1，表示起始各个情况都没出现过
5.记忆条件：mem[k][V]>=0，表示以前这个情况出现过，直接返回以前的值
6.边界条件（初值）：if(k==n+1)return 0;//无物品可选，获得的价值最大为0
3.AcWing1371.货币系统
完全背包求方案数
一：完全背包迭代法递推法
1.状态表示：f[i][j]：考虑在前i种货币中选，刚好凑好j元钱的方案数
2.朴素版状态转移方程： f[i][j]+=f[i-1][j-k*a[i]];（多一层循环枚举k，会超时）
3.优化版状态转移方程： if(j>=a[i])f[i][j]+=f[i-1][j]+f[i][j-a[i]];
else f[i][j]+=f[i-1][j];（省略了一些重复计算部分）
4.初值：f[0][0]=1;//0种货币凑成0元也是一种方案数
二：完全背包记忆化搜索递归回溯法
1.记忆化数组状态表示:mem[k][V]:考虑第k种到最后一种中选，刚好凑成v的方案数
2.朴素版递归搜索（状态转移）（多一层循环枚举k，会超时）：
for(int i=0;i*a[k]<=v;i++)
res+=dfs(k+1,v-i*a[k]);
3.优化版递归搜索（状态转移）（省略了一些重复计算部分）：
int res=0;
if(v>=a[k])res+=dfs(k,v-a[k])+dfs(k+1,v);
else res+=dfs(k+1,v);
4.记忆数组初始化：mem[i][j]全为-1，表示起始各个情况都没出现过
5.记忆条件：mem[k][V]>=0，表示以前这个情况出现过，直接返回以前的值
6.边界条件（初值）：
if(k==n+1)
if(v==0)return 1;//0种货币凑成0元也是一种方案数
else return 0;
