leetcode背包问题拓展（C++）

目次
1.一和零（二维费用的背包问题）
2.盈利操持
3.组合总和IV（似包非包）
4.不同的二叉搜刮树（卡特兰数）
<hr>  
1.一和零（二维费用的背包问题）

现在有m个0和n个1，从字符串数组里挑字符串，让全部字符串的0/1加起来分别不超过m/n，返回最多可以挑多少个字符串
   什么是二维费用的背包问题？
  一维费用指只有一个背包体积作为限制，二维费用指会有 0、1 两个东西作为限制条件
  二维费用的背包问题即二维费用的01背包问题
  <hr>  1.状态表示
  dp[j][k]：从前i个字符串中选，字符0的个数不超过j，字符1的个数不超过k，全部的选法中最大的字符串个数（是用01背包问题的头脑推得的）
  2.状态转移方程
  不选str：0、1 的个数都没变，dp[j][k] = dp[i-1][j][k]
  选str：假设str的0个数为a，1个数为b，那么 dp[j][k] = dp[i-1][j-a][k-b]（分析如下图所示），这边要的是字符串个数，以是还必要在整个式子后面 + 1
  j >= a && k >= b 是选str的先决条件
  3.初始化
  与01背包问题一样， j 、k 不会有数组越界的情况，以是我们只必要考虑 i
  三维数组要对 i 、j 、k 都+1，i == 0 时即下图 k 轴与 j 轴所围成的平面（该平面就相当于01背包问题里的第0行全部列）
  i == 0 即什么字符串都还没有选，以是把整个平面初始化为0即可
  4.填表顺序
  只必要保证 i 是从小到大即可（在图上就是由远及近）
  5.返回值：

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。