【回复就加米】求比较动态规划专题课程

如题，最近看到地主家有推荐educative的 dp的课程，大概40多刀（详见link）https://www.educative.io/courses ... r-coding-interviews


还有就是九章算法的dp专题

想问下有小伙伴上过这两家的课程吗？感觉怎么样呢，以及有其他dp课程推荐吗

最近被dp搞得实在恶心。祝大家offer多多

楼主你好，我没有上过那两个课程，但是学过一些其它关于dp的资料，感觉对我来说非常有用，希望对你有帮助。

主要推荐mit这个公开课里的dp，lecture 19 -22[1]。他把dp讲的非常清楚，而且还有很多例子。我当时听完感觉对dp的理解加深了很多。还有就是coursera上的algorithm(Stanford 开的那门)， 那门课程我是全部跟完了，整体讲的非常清楚，里面有一部分是关于dp的，讲的挺好的。mit那个有四个lecture，内容更加详细。

[1] https://ocw.mit.edu/courses/elec ... cci-shortest-paths/

https://zxi.mytechroad.com/blog/category/dynamic-programming/

https://leetcode.com/discuss/gen ... rogramming-Patterns
https://leetcode.com/discuss/gen ... ns-sample-solutions
https://leetcode.com/discuss/gen ... teps-to-be-followed
https://leetcode.com/problems/ra ... tuitive-explanation
https://leetcode.com/problems/lo ... tions-Helpful-Notes
https://leetcode.com/problems/mi ... ue-%3A-step-by-step
https://leetcode.com/problems/mi ... ok-2-hours-to-solve

https://medium.com/better-progra ... amming-54902b6b0071

https://www.kancloud.cn/kancloud/pack/70124

https://www.hackerearth.com/prac ... ramming-1/tutorial/

still on-going:
https://github.com/zea7ot/lc-jav ... dynamic_programming

我的理解是DFS加记忆化与DP是等同的。搜索加记忆是recursive的写法，DP是iterative的写法。核心是要找到overlap的子问题。我一般是先想爆搜的解（比如有2^N种），然后想想搜索过程中有没有子问题是重叠的，然后你会发现原来爆搜重复查询了很多次（比如说子问题实际上只有N^2种，只要把这些子问题的解都记录下来就行了）。然后就自然可以得到子问题的表达方式以及不同子问题之间的关系（状态以及状态转移方程）。

LC里的官方讲解不够嘛？

K哥 发表于 2020-06-26 11:45:37
LC里的官方讲解不够嘛？

感觉官方题解有时候技巧性蛮强的，想找一些框架式解法

hellokk404 发表于 2020-06-26 15:11:26
感觉官方题解有时候技巧性蛮强的，想找一些框架式解法

dp有框架式的解法吗。。。我表示怀疑感觉许多时候dp能做dfs也能做，网课我感觉大概率也就是见题拆题。。

拥抱广阔世界 发表于 2020-06-26 15:59:04
dp有框架式的解法吗。。。我表示怀疑感觉许多时候dp能做dfs也能做，网课我感觉大概率也就是见题拆题。。

你说的有道理，就是dp可能框架比较多，光有一两个解不出所有，因此想用网课穷举lol

拥抱广阔世界 发表于 2020-6-27 06:59
dp有框架式的解法吗。。。我表示怀疑感觉许多时候dp能做dfs也能做，网课我感觉大概率也就是见题拆题。。

其实换句话说，dfs 或者 backtracking 能做的，dp 都能。。。，其实我看地里有的人说套路很明显，我还是没get 到lol

zzh372024750 发表于 2020-06-26 16:14:05
其实换句话说，dfs 或者 backtracking 能做的，dp 都能。。。，其实我看地里有的人说套路很明显，我还是没get 到lol

DFS能做的dp不一定能吧，，拓扑序列这种dp能吗。。。

hellokk404 发表于 2020-06-26 16:05:16
你说的有道理，就是dp可能框架比较多，光有一两个解不出所有，因此想用网课穷举lol

hhhh glhf，我反正就是肯放弃，实在做不出来就放弃lol

拥抱广阔世界 发表于 2020-6-27 07:50
DFS能做的dp不一定能吧，，拓扑序列这种dp能吗。。。

hhhh  一句话揭露我学艺不精

zzh372024750 发表于 2020-06-26 17:30:40
hhhh  一句话揭露我学艺不精

这两天刚好做到了类似的题，，真的太难了。。orz