给一个数字n,表示n个人, 给一个数字p, 表示最小的收益, 给两个数组,表示工作和工作需要的人, 问最多使用n个人并且满足最小收益的工作一共有多少种组合? 这个题一眼肯定是动态规划, 但是因为是求多少种组合, 所以每个条件都单做一维. Let dp[i][g][p] to be the first i’th jobs (including) with exact g members used and having exact p profit. 首先要初始化这个dp, 那么dp[0][0][0]是1 从背包问题,宽泛考虑, 可以知道, 如果不选当前的i, 那么对应的g和p就不会增加, 所以这也是一种组合: 当决定了选i’th job, 就要考虑当前i是否满足限制人数(不满足则不选): 通过上面这行后, 确定了ith job肯定能干, 接着考虑下面的, 如果ith job的profit和当前profit加起来超过了P(最小profit), 因为其实超过了多少无所谓, 我们就把所有超过P的job放到P的位置上, 这样便于统计. 如果加起来还是没有超过p, 那么我们只能先存着, 因为当前的运算可能作为以后某个答案的子集. 以上就是dp的构建, 最后的答案因为我们的dp只迭代了包含前i个job的子问题, 子问题并没有对人数进行迭代, 人数从0到G都是满足题意的答案, 所以需要在dp的中找到这些答案并且加起来. 全代码: