算法小技巧-动态规划
这篇文章灵感来源于今天的leetcode的每日一题
其实就是很明显的多维的背包问题，但是题目问的是不少于minProfit的种类数
最开始我定义的转移方程是dp[i][j]表示i个人挣j的钱，然后最后再统计大于minProfit的方案数
但是超时了，看了题解后发现，应该定义dp[i][j]为i个人挣至少j的钱
那么这样我们最大k的枚举范围也才到minProfit，不需要枚举总共的sum
所以最终的答案就是dp[n][minProfit]
这里还有个小细节，就是如果最开始初始化只是dp[0][0] = 1的话，那么最后统计就要从1个人统计到n个人，如果最开始的初始化是dp[i][0] = 1，i从0到n，那么最后只需要dp[n][minProfit]的结果就好
因为取决于我们状态的定义，究竟是具体i个人，还是至多i个人
那么方程的转移就是dp[i][j] += dp[i - group][max(0, j - profit)]
那么这时候大家可能就会有疑惑了，后面取了max还能统计全部的状态吗
注意我们这里是统计至少挣j的钱，那么dp[i][0]基本上包含了所有的方案，因为我们的利润不会是一个负数
所以如果感觉总利润会超出去很多的话，实际上是因为我们大多数的方案数都存到了dp[i][0]里
总之是对动态规划灵活运用的一个例子，希望好好理解
文章评论