0-1背包问题（完全背包问题）的二维/一维，正序/倒序遍历的完全理解
·
反正关于遍历顺序和二维转一维的过程，我看csdn，b站上没有讲的很清楚的，这里简略写一下，后面如果有时间了就更新成代码和视频动画讲解，
完全理解二维化一维过程中的遍历顺序问题 首先如果需要二维化一维，必须满足当前状态只受表格左侧一列的影响，例如01背包问题，根据（无论j>= space_i 还是 j <space_i）状态转移方程，第i物品能不能放进去只受前一列i-1的影响，因此可以得出两个结论，第一最外围的for(i)的循环是正序遍历，第二可以化为一个不断更新的一维数组，这个一维数组每次新的i循环中dp[j]从后向前遍历，为何从后向前遍历呢，这就由于转移方程和物品唯一性决定的，转移方程告诉我们dp[i][j]受到dp[i-1][j-space_i]的影响，到一维里边就是准备更新的dp[j]受到上一轮循环继承而来的未更新的dp[j-space_i]的影响，所以不能先正序更新前面的，否则可能会多次使用i物品，例如当j-space_i仍然大于space_时，dp[j-space_i]会放入j，当正序遍历到dp[j]时，还是可以放入i，因此造成了多次使用i，就变成了完全背包问题（同样的物品可以多次放入），因此，综上所述，外层i正序遍历，内层j倒序遍历，由二维化为一维dp。
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
3
0- 0
已为社区贡献1条内容
所有评论(0)