关于leetcode474题遍历顺序的一个小疑问
来源：9-7 面试中的0-1背包问题 Partition Equal Subset Sum
v不离不弃v
2020-05-26
波波老师，今天在做477题的时候，判断这个是一个很纯粹的01背包问题（准确的说是多重背包），背包的容量分别是0和1的个数m和n，要填的东西为字符串数组中的0 1数目，思路很简单，但是这类问题涉及到多维度的话，那么在细节中的把握个人觉得比较麻烦—>比如便利的顺序问题（通常在优化空间方面体现），因为我开始从前向后进行找规律的时候，发现会重复，比如剩余 0 1 or 1 0的时候会重复计算，这个时候我就陷入了沉思—>我的 0 1背包思路到底对不对，但是思考了很久之后觉得思路是没问题的，就是在填背包的时候的方向不对，于是尝试用笔画出从m n 开始到0 0 的顺序的遍历结果，发现对了。
所以我就有疑问，对于背包问题的遍历顺序，难道只可以通过画图的方式来事先模拟一遍才可以得出么？那么对于多维背包，这个工作量就变得稍许庞大，在面试中很可能会消耗很多时间-。-，请问有什么好的方法嘛？还是只可以慢慢按步骤来，反正不是从前向后就是从后向前，要么从上到下或者从下向上~~~~通过纯粹的手动模拟的方式找到最终的遍历顺序呢？
2回答
-
liuyubobobo
2020-05-26
背包问题在做空间优化的时候使用从后向前的遍历算是一个挺标准的技巧。在这个课程中介绍背包的优化的时候，印象里介绍过。
思考的话，可以这么想：
你的状态转移方程式 dp[k][i][j] = max(dp[k - 1][i - zero][j one]) for every i, j
所以，计算 k 的状态，依靠 k - 1 的状态，不仅如此，计算 k 的 i， j 状态，依靠的 k - 1 的 i, j，肯定更小！（因为是减法）。
所以，我们要想扔掉 k 这个维度，在计算 dp[k] 的时候，dp 里存的是 k-1 的状态。在计算更大的 i,j 的时候，还需要更小的 i,j，所以这些更小的 i,j 不能覆盖掉，要等更大的 i,j 计算完。所以，就需要从后向前遍历了。
继续加油！：）
012020-05-26 -
liuyubobobo
2020-05-26
题号是否有误？477 的函数签名是：public int totalHammingDistance(int[] nums) ？
012020-05-26
相似问题