请问这两个memo[i]有什么区别？为什么要这样写?比如i=2时，右边那个memo[i]不是没有初值吗？怎么比较？

Question

Answer 1

提问者 蒙特卡洛 2019-07-24 20:52:56

我参考的剑指OFFER上的

老师它这里两边都相当于考虑用memo[i]来计算，所以只需要分解一半就行了，但是我没懂得是它这里为什么只需要比较max和每次计算出的product[j]*product[i-j]的大小，不需要考虑和j*(i-j)比较大小了吗？

而且我单步debug出来的长度为4时，最大乘积应该为4(2*2)，它这样算出来就是3了。

• liuyubobobo #1

  因为对 2 和 3，它使用硬编码的方式返回，同时对memo[2]和memo[3]手动赋值。可以试一下，去掉对memo[2]和memo[3]的赋值，算法就是错误的。2和3是唯一两个不要继续分解下去，结果比分解还要小的数。而课程程序中比较j*(i-j)，就是在比较对i - j不再继续分下去了。另：你的跟踪应该有错，这个程序计算出的memo[4]是4。看一下你说的3是不是只是中间结果，不是最终结果。

• 提问者 蒙特卡洛 回复 liuyubobobo #2

  我的memo[4]结果确实是4，第一张图就是我的结果，我是想问第二张图中，product[1]代表的是长度为2的结果，prodcut[2]代表的是长度为3的结果，这都对，为什么product[3]对应长度为4的结果会是3呢？是它写错了吗？还是我理解错了？product[3]是指的什么？

• 提问者 蒙特卡洛 回复 liuyubobobo #3

  老师你的意思是说2和3是仅有的两个不需要继续分解，因为分解后的乘积比自身还要小，所以直接用自身的值，在前面强行赋值给P[2]和P[3]是吗？
  他因为把2和3单独提了出来，所以后面的算法中没有考虑j*(i-j),
  而我们的通用性更好，把2和3也加了进来，所以需要考虑j*(i-j)?

点开查看后面3条评论

Answer 2

liuyubobobo 2019-07-24 01:31:12

在Java语言中，int的初始值是0。new 完整个数组空间，所有的数都是0。打印出来试试看？

memo[i - j] 并没有重新算。最外层对 i 的for循环，每一次都会决定好一个memo[i]的值，之后，就记录在memo[i]了。之后，计算更大的memo[i]的时候，i - j 一定是比当前的 i 小，所以memo[i - j] 一定已经计算完了，直接拿出来就用了。注意，memo[i - j] 这个写法就是取出 memo 数组中 i - j 位置的结果而已，不涉及其他计算。

强烈建议使用一个小数据，比如 n = 10，实际跟踪一下整个算法，看一下整个算法到底是怎么计算出每一个memo[i] 的？

对于那句max3，代码太压缩，可能不好跟踪，可以替换成下面的样子，实际看一下在每次内层循环中，a,b,c都是谁？为什么是这些数字？最后决定了memo[i]是多少？

for(int i = 2; i <= n; i ++)
    // 求解 memo[i]
    for(int j = 1; j <= i; j ++){
        int a = memo[i];
        int b = j * (i - j);
        int c = j * memo[i - j]; // 在这里一定要看一下 memo[i - j] 是多少？为什么？
        memo[i] = max3(a, b, c);
    }

继续加油！：）

• 提问者 蒙特卡洛 #1

  谢谢老师，我先试试

• 提问者 蒙特卡洛 #2

  谢谢老师！

• 提问者 蒙特卡洛 #3

  老师我还有个问题写在回复里面了，麻烦你看看

Answer 3

提问者 蒙特卡洛 2019-07-23 22:47:10

还有这里并没有单独保存memo[i]的值，那么后面当i++后算memo[i-j]的值不是要重新算吗？怎么直接用之前已经算了的memo[i]呢？比较晕........请老师讲解一下