找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6554|回复: 26
收起左侧

[刷题总结] 【学习小结】动态规划

  [复制链接]

90

主题

46

精华

1909

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1909

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-12-2017 08:07 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
边学边记边总结。还在学习中,希望大牛们能多多指教。
==========================================================
上个转载
http://blog.csdn.net/fightforyourdream/article/details/19755859
http://blog.csdn.net/linhuanmars/article/details/38468361

==========================================================
挖个坑。打算把遇到过的LeetCode里的可以使用“递归->动态规划”的优化思路的题目总结一下。

http://www.meetqun.net/thread-771-1-1.html 这个题目Climbing Stairs已经讨论得很详细了。
http://www.meetqun.net/thread-752-1-1.html Unique Binary Search Trees
==========================================================

有一种问题, 他的求解是可以既使用递归,又使用动态规划的。
这种题目有什么特点呢?
1)有初始解。比如n=1时返回0等等
2)有递推公式。比如F(n) = F(n -1) + F(n-2)

初始解往往属于显式条件,比较容易得出来。
递推公式则需要读者自己判断 1)是否有解决某一问题的pattern, 2) 对于特定的k, n (k < n), solution(k)能否被用于生成solution(n)呢?

当我们找到了一类问题的初始解和递推公式时,咱们不应该只满足于做出来这道题了。而是应该有一个层层递进的优化思路了。

一个通用的优化思路可以是
1. 递归 Recursion。
2. 储存历史结果的递归 Recursion + Memoization。
3. 空间复杂度较高的动态规划 (二维或一维)???
4. 空间复杂度较低的动态规划 (常量)????

至于哪些问题可以按照这样的方式来层层递进的优化,我们都需要多思考思考。




本帖被以下淘专辑推荐:

10

主题

4

精华

678

积分

超级会员

Rank: 4

积分
678
发表于 12-14-2017 05:59 AM | 显示全部楼层
mengma刷的很快啊..
回复 支持 反对

使用道具 举报

13

主题

11

精华

1816

积分

顶级会员

Rank: 6Rank: 6

积分
1816

最佳新人活跃会员热心会员

发表于 12-14-2017 06:01 AM | 显示全部楼层
mark! DP我一直做的稀里糊涂的,感谢楼主开帖总结
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表