前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >动态规划

动态规划

作者头像
刘开心_1266679
发布2019-02-14 15:33:18
7240
发布2019-02-14 15:33:18
举报
文章被收录于专栏:开心的学习之路

动态规划(dynamic programming)是求解决策过程(decision process)最优化的数学方法。一般分为:

线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;

区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等;

树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等;

背包问题:01背包问题,完全背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等; 动态规划的特点: ------把原始问题划分成一系列子问题(与分治法相同) ------求解每个子问题仅一次,并将其结果保存在一个表中,以后用到的时候直接取 ------自底向上地计算(分治法自顶向下,没有考虑子问题重叠) 适用范围: ------优化问题:可分为多个相关子问题,子问题的解被重复使用 使用动态规划的条件 ------优化子结构(保证动态规划的正确性):当一个问题的优化解包含了子问题的优化解时,我们说这个问题具有优化子结构。如果不具有优化子结构,保存结果就没有意义了,反而浪费了空间。 ------重叠子问题:在问题的求解过程中,很多子问题的解将被多次使用 动态规划算法的设计步骤: ------分析优化解的结构 ------递归地定义最优解的代价 ------自底向上地计算优化解的代价保存之,并获取构造最优解的信息 ------根据构造最优解的信息构造优化解 动态规划的核心是状态和状态转移方程。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015年03月12日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档