动态规划之二维费用的背包问题解析

以leetcode474题为例引出概念

题目解析： 

给一个m和一个n，m表示最多有多少个0，n表示最多有多少个1，

选出来的子集，记录0和1的个数，在不超过的情况下能选的最大子集，也就是能选多少个元素

从这里，如果观察敏锐的话，可以发现这是一个背包问题，就是选一堆东西，不能超过巴拉巴拉

但这里是有两个背包，也就是m和n，所以这就叫二维背包问题

就是由原来的一个体积限制，到现在的体积和重量限制

m和n就是两个限制

算法原理：

类比我们就可以推出状态表示

 

 通过前面的学习，我们已经可以快速的写出状态表示方程

注意：用a表示str[i]中的0的个数，用b表示1的个数

注意：只有当j>=a&&k>=b时才存在第二种

然后对这两种情况取最大值即可

初始化：

我们发现在填表的时候哪个地方会越界就初始化哪

但是根据我们前面的学习，当j==0和k==0时是不用初始化的，因为会判断

只有当i=0时需要初始化，根据状态表示，i=0表示数组里面有0个子串，不能超过j和k，所以填0

建表的时候就会自动初始化为0，所以不用单独填

 

代码编写：