关于leetcode474题遍历顺序的一个小疑问

Question

波波老师，今天在做477题的时候，判断这个是一个很纯粹的01背包问题（准确的说是多重背包），背包的容量分别是0和1的个数m和n，要填的东西为字符串数组中的0 1数目，思路很简单，但是这类问题涉及到多维度的话，那么在细节中的把握个人觉得比较麻烦—>比如便利的顺序问题（通常在优化空间方面体现），因为我开始从前向后进行找规律的时候，发现会重复，比如剩余 0 1 or 1 0的时候会重复计算，这个时候我就陷入了沉思—>我的 0 1背包思路到底对不对，但是思考了很久之后觉得思路是没问题的，就是在填背包的时候的方向不对，于是尝试用笔画出从m n 开始到0 0 的顺序的遍历结果，发现对了。
所以我就有疑问，对于背包问题的遍历顺序，难道只可以通过画图的方式来事先模拟一遍才可以得出么？那么对于多维背包，这个工作量就变得稍许庞大，在面试中很可能会消耗很多时间-。-，请问有什么好的方法嘛？还是只可以慢慢按步骤来，反正不是从前向后就是从后向前，要么从上到下或者从下向上~~~~通过纯粹的手动模拟的方式找到最终的遍历顺序呢？

Answer 1

liuyubobobo 2020-05-26 08:35:29

背包问题在做空间优化的时候使用从后向前的遍历算是一个挺标准的技巧。在这个课程中介绍背包的优化的时候，印象里介绍过。

思考的话，可以这么想：

你的状态转移方程式 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 计算完。所以，就需要从后向前遍历了。

继续加油！：） 

• 提问者 v不离不弃v #1

  奥，我明白啦，我记得您给的题里面有个是从上到下遍历的-。-，还有个是从左向右遍历的，感觉dp问题的思路较为统一，但是在解决的过程中的规律还需要通过总结来找到-。-

Answer 2

liuyubobobo 2020-05-26 05:06:11

题号是否有误？477 的函数签名是：public int totalHammingDistance(int[] nums) ？

• 提问者 v不离不弃v #1

  是474题，看错了......写了一下午题目...这个题目的空间优化是从一个三维数组优化而来，但是这个数组是立体的哇，根本想不出来哇-。-直接定义一个二维的就不知道如何遍历了-。-从前向后会导致数据重复，所以是不是发现这个问题，就要反过来思考呢？