这篇文章是本人学习背包dp的阶段性总结,涵盖了本人的心路历程和思考:
总结一:枚举的方式及本质。
考虑状压dp。
当n比较小时(n <= 128),忽略是否合法,完全可以用一串二进制数字表示选择方案。
如:
当n = 7时,0001101即可表示选择了第1,3,4件物品(从右开始)。
而由于多数情况下,n > 128,导致使用状压会超过c/c++的最大范围__int128,即不能使用状压。
但这种枚举的思想,却是奠定了记忆化搜索的基础。
总结二:背包dp自记忆化搜索而生。
初学背包dp时,最先接触的一定是最经典的01背包: