请问这两个memo[i]有什么区别？为什么要这样写?比如i=2时，右边那个memo[i]不是没有初值吗？怎么比较？
来源：9-3 发现重叠子问题 Integer Break
蒙特卡洛
2019-07-23
3回答
-
蒙特卡洛
提问者
2019-07-24
我参考的剑指OFFER上的
老师它这里两边都相当于考虑用memo[i]来计算，所以只需要分解一半就行了，但是我没懂得是它这里为什么只需要比较max和每次计算出的product[j]*product[i-j]的大小，不需要考虑和j*(i-j)比较大小了吗？
而且我单步debug出来的长度为4时，最大乘积应该为4(2*2)，它这样算出来就是3了。
062019-07-25 -
liuyubobobo
2019-07-24
在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); }继续加油！：）
032019-07-24 -
蒙特卡洛
提问者
2019-07-23
还有这里并没有单独保存memo[i]的值，那么后面当i++后算memo[i-j]的值不是要重新算吗？怎么直接用之前已经算了的memo[i]呢？比较晕........请老师讲解一下
00
相似问题