leetcode343的一个小问题

Question

波波老师，leetcode343这题，在求取最大值的时候，那个只考虑分成2部分的比较

memo[i] = max3(memo[i], j * (i - j), j * memo[i - j]);

真的好难想出来哇，请问，这个只分成2部分的j * (i - j)可以不写嘛？因为我感觉我打死也不会想到哇，请问为什么加入这句话呢，波波老师可以解释下吗？还有，在memory search中，您加入了Arrays.fill(memo, -1);这句话，请问在dp写法中，不对memo赋值会不会影响max3的比较呢？我试着加上了这句话发现复杂度高了很多。。。
题外话：我感觉动态规划好难哇，感觉要复习数学了。。。最近忙着应付数据库考试，刷题什么的放了好久，哎。。

Answer 1

liuyubobobo 2020-04-20 07:09:23

1.

对于记忆化搜索来说，把所有 memo 设置成 -1，是一个标记，也就是 memo[x] == -1 的时候，代表 x 这个状态没有搜索到；否则代表 x 这个状态搜索过了，就不用了搜索了，直接返回 memo[x] 就好了。

这样做有一个前提，就是 memo[x] 的值不能等于 -1，在这个问题中是满足的。实际上，因为在这个问题中，memo[x] 的值不能为 0，所以，不赋这个初值，用默认的初始值 0 来标记状态是否计算过，也是 ok 的。这里的关键是，需要一个标记，来看出来一个状态有没有被搜索过，以避免重复搜索。

2.

分成三部分的原因是，对于 1 个 i，j * memo[i - j] 表示的是给他拆分成 3 个或者 3 个以上的元素；但是，一个 i 有可能只被拆分成两个元素，那就是 j * (i - j) 了。

将  j * (i - j) 扔掉，看看会不会出错？在什么测试用例下会出错？实际调试跟踪一下，为什么出错了？

P.S. 动态规划确实有难度。对计算机专业来说，也是很难的一类算法设计问题。我个人觉得其实复习数学对做好动态规划，尤其是面试难度的动态规划问题意义没那么大。多做一些动态规划，慢慢就有感觉了。动态规划至少做 20 道才算入门。100 道应该就能熟练掌握了。Leetcode 上的动态规划就有 100 多道，并且大多数周赛的 hard 题木其实都是动态规划。

加油！：）

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

  奥，波波老师我明白啦，这段时间我应该都会一直做dp的，然后dp和贪心昨晚之后我就开始吧之前您布置的100多道乐儿天聪的题目再写一遍，然后总结。感觉之前做的好多都忘了。。。。