1回答

liuyubobobo

2020-04-20

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 题木其实都是动态规划。

加油！：）

0

1

v不离不弃v

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

2020-04-20

共1条回复