0%

背包问题

01背包:有限物品数量

二维01背包问题,两个for循环可以交换顺序,内层for循环方向可以顺序循环

一维01背包问题:因为物品数量有限,内层for循环不能重复取,必须倒序,两个for循环可以交换顺序

完全背包问题:物品可以重复取

二维:for循环可以交换顺序,内层for循环必须顺序,因为物品可以重复取

一维:for循环可以交换顺序,内层for循环必须顺序,因为物品可以重复取

求方法数:dp[j]+=dp[j-nums[i]]

一维:求组合数:先遍历物品再遍历背包

求排列数:先遍历背包再遍历物品