近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1364|回复: 6
收起左侧

[动态规划] 有没有什么适合自学dp的教程和网站

[复制链接] |试试Instant~ |关注本帖
mdzzxswl 发表于 2016-6-23 12:01:38 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
本渣只上过data structure没上过算法课 dp啊max overflow啊什么的都没学 但面试不都问这些吗=。=就想说自学一下 看了看cracking interview怎么只讲了fibonacci啊。。。。
想问下地里各位爸爸。。。。有什么网站或教程学dp比较好。。。。。谢谢爸爸们
leetcode有刷啊 但是 看到dp 就 头疼了。。。。
Eddyz 发表于 2017-1-17 10:34:22 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
动态规划(DP: Dynamic Programming

一、基本思想与策略

基本思想与分治法类似,也是将待求解的问题
    - 分解为若干个子问题(阶段)
    - 按顺序求解子问题,
    - 前一个(或前有限个,一般不超过三个)子问题的解,为后一子问题的求解提供了有用的信息。
    - 在求解子问题时,需要求得各种可能的解。这些解是累计关系,是当前子问题的最终解。
    - 依次解决各子问题,最后一个子问题的解就是初始问题的解。

动态规划的子问题可以用来判定结果的最短子问题,或是前后两个,或是前后三个,总之是有限个。
由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,
可将子问题及其输出保存在一个二维数组中。

与分治法最大的差别是:
适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的,
即下一个子问题的求解是建立在上一个(几个)子问题的解的基础上进行求解。


二、动态规划过程

每次决策需要依赖于以前的状态,随即又产生新的状态。
每步都选择最优状态,但是其它状态也需要保留,以便为后面的决策提供依据。
一个决策序列就是在变化的状态中产生出来的,所以这种多阶段最优化决策解决问题的过程就称为动态规划。

三、例子:最佳买股票时机(四种情况)

1、Best Time to Buy and Sell Stock -- LeetCode
http://blog.csdn.net/linhuanmars/article/details/23162793

2、Best Time to Buy and Sell Stock II -- LeetCode
http://blog.csdn.net/linhuanmars/article/details/23164149

3、Best Time to Buy and Sell Stock III -- LeetCode
http://blog.csdn.net/linhuanmars/article/details/23236995

4. Best Time to Buy and Sell Stock with Cooldown
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

上面四道题是循序渐进的。做完后可以基本理解DP了。
DP 的过程就像是做乘法运算,把每位的值都分开乘,然后记录进位,然后累加,最后得结果。大概意思是这样的。


-
回复 支持 1 反对 0

使用道具 举报

ryancooper 发表于 2016-6-23 12:55:29 | 显示全部楼层
关注一亩三分地微博:
Warald
想要一劳永逸不可能。。。好的tutorial的话可以看看topcode的
https://www.topcoder.com/communi ... novice-to-advanced/
回复 支持 1 反对 0

使用道具 举报

 楼主| mdzzxswl 发表于 2016-6-23 12:03:34 | 显示全部楼层
算法导论这本书 感觉 又有点 太深(????
想说有什么一劳永逸的tutorial啊(摊手
回复 支持 反对

使用道具 举报

cptn3m0 发表于 2016-6-30 09:57:11 | 显示全部楼层
我看了很多资料, 都说要多做题, 体会一下
回复 支持 反对

使用道具 举报

kamibear 发表于 2017-1-15 11:36:16 | 显示全部楼层
搜中文博客 看看那个IO的大神的讲解
回复 支持 反对

使用道具 举报

在浙里 发表于 2017-1-17 23:08:40 | 显示全部楼层
楼主这个爸爸叫的人发
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-24 22:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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