能否推荐一些综合型题目，以及 L560 题的一个小问题
来源：7-6 稍复杂的递归逻辑 Path Sum III
Poplar_hills
2019-10-24
Dear bobo 老师，
我在解决 560号题 时发现这道题真是非常之好，原因如下：
4个 solution 循序渐进，逐渐将时间复杂度从 O(n^3) 降低至 O(n)；
应用了多个章节中的知识点和解题思路，如：双指针滑动思路、缓存累加和思路、Two Sum 的哈希表思路；
应用了多种数据结构：Array、Map。
这样的题目非常有助于将各个知识点融会贯通，快速提升 problem-solving 的能力。不知道 bobo 老师是否能再多推荐一些这样的题目？
PS：还想顺便请教老师一下，这道题的 Solution 2 是否能算作 DP 解法？看上去有点像 DP，但又写不出来状态转移方程。
非常感谢！
写回答
1回答
-
Solution 2 不算动态规划。其实是一个很经典的套路，我一般管它叫 Presum，是在求解区间求和相关问题的时候，经常使用的一种技巧：）
至于综合性的题目，这个看不同人对综合性的理解了。这个水平的题目，大概是每周 Leetcode 周赛第三题（有的周难一些，大概是第二题）的程度。有兴趣的话，可以把 Leetcode 周赛的第三题大概都看一看：）
继续加油！：）
012019-10-25
相似问题