找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 7558|回复: 4
收起左侧

[刷题总结] 动态规划 (Dynamic programming)

[复制链接]

12

主题

7

精华

382

积分

高级会员

Rank: 3Rank: 3

积分
382

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

发表于 12-19-2014 11:12 PM | 显示全部楼层 |阅读模式

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

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

x
一直没理解动态规划,那就从它的定义看,帮助自己理解。
下面摘自百度百科,知道前因后果就容易理解哪些属于动态规划了。

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming,这是该领域的第一本著作。

分类:
动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。
举例:
线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等
区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等
树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等
背包问题:01背包问题,完全背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等

概念意义:
动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不像搜索或数值计算那样,具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法,而不存在一种万能的动态规划算法,可以解决各类最优化问题。

基本结构:
多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动态规划方法。

基本模型:
多阶段决策过程的最优化问题。含有递推的思想以及各种数学原理(加法原理,乘法原理等等)。
在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。当然,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展,当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线。
它包含了以下几种基本模型:
(1)确定问题的决策对象。 (2)对决策过程划分阶段。 (3)对各阶段确定状态变量。 (4)根据状态变量确定费用函数和目标函数。 (5)建立各阶段状态变量的转移过程,确定状态转移方程。
状态转移方程的一般形式:
一般形式: U:状态; X:策略
  顺推:f[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]} 其中, L[Uk-1,Xk-1]: 状态Uk-1通过策略Xk-1到达状态Uk 的费用 初始f[U1];结果:f[Un]。
倒推:
  f[Uk]=opt{f[Uk+1]+L[Uk,Xk]}
  L[Uk,Xk]: 状态Uk通过策略Xk到达状态Uk+1 的费用
  初始f[Un];结果:f(U1)

解决的常见的问题:
在编程中常用解决最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线等问题

摘自: baike.baidu.com/link?url=LamPSbl3445BDJa8syefSeYv9z5Ma2FgLXRkE1k3YdPuYSms6B86MPA6vxuUHP9SgTaK8njaXEhXOac-7FYr5K


21

主题

4

精华

243

积分

高级会员

Rank: 3Rank: 3

积分
243
发表于 12-20-2014 12:02 AM | 显示全部楼层
关于DP,强烈推荐这个网站上的几个例题视频教程。讲解的非常好:
http://people.cs.clemson.edu/~bcdean/dp_practice/
回复 支持 反对

使用道具 举报

12

主题

7

精华

382

积分

高级会员

Rank: 3Rank: 3

积分
382

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

 楼主| 发表于 12-20-2014 12:51 AM | 显示全部楼层
洋葱 发表于 12-20-2014 12:02 AM
关于DP,强烈推荐这个网站上的几个例题视频教程。讲解的非常好:
http://people.cs.clemson.edu/~bcdean/dp ...

好的,多谢多谢。
我结合leetcode的题再看看这些资料理解理解。有更多的理解再继续更新。

回复 支持 反对

使用道具 举报

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

本版积分规则

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