动态规划

基本思想:将待求解问题分解成若干子问题,先求解子问题,然后从子问题的解中得到原问题的解。

与分治不同的是,经分解得到的子问题往往不是互相独立的。

若用分治法来解这些问题,则得到的子问题数目太多,以至于最后解决原问题需要消耗指数时间。

步骤设计

1 找出最优解的性质,并刻画其结构特征

2 递归地定义最优值

3 以自底向上的方式计算出最优值

4 根据计算最优值得到的信息,构造最优解

应用实例:

矩阵连乘问题

最长公共子序列

最大子段和

凸多边形最优三角剖分

多边形游戏

图像压缩

电路布线

流水作业调度

背包问题

最优二叉搜索树

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习自然语言处理

【概率笔记】条件概率这样学才快啦

比如,一个上学期间整天鬼混的学沫,根本就不好好学习,对于他而言,选择题的四个选项ABCD被他选取的概率就为1/4。而对于大学霸来说,题题都会,那么他选取每一个选...

893
来自专栏菩提树下的杨过

NDArray自动求导

NDArray可以很方便的求解导数,比如下面的例子:(代码主要参考自https://zh.gluon.ai/chapter_crashcourse/autogr...

22910
来自专栏书山有路勤为径

目标跟踪与定位——状态与定位

卡尔曼滤波器可以结合不准确的传感器测量和稍微不准确的运动预测,以获得比仅来自传感器读数或仅有关运动的任何更好估计位置。

2382
来自专栏钱塘大数据

32类计算机与数学领域最为重要的算法

导读: 奥地利符号计算研究所的Christoph Koutschan博士在自己的页面上发布了一篇文章,提到他做了一个调查,参与者大多数是计算机科学家,他请这些科...

3028
来自专栏PPV课数据科学社区

【大数据问答】SPSS是如何做到发现数据质量问题,例如,如何发现缺失值?

SPSS是如何做到发现数据质量问题,例如,如何发现缺失值? (1)系统缺失值、空白值 每一个变量均有可能出现系统缺失或者空白,当数据量巨大时我们根本无法用眼睛...

4124
来自专栏贾志刚-OpenCV学堂

基于积分图的二值图像膨胀算法实现

积分图来源与发展 积分图是Crow在1984年首次提出,是为了在多尺度透视投影中提高渲染速度。随后这种技术被应用到基于NCC的快速匹配、对象检测和SURF变换中...

5118
来自专栏数据结构与算法

P3819 松江1843路

题目描述 涞坊路是一条长L米的道路,道路上的坐标范围从0到L,路上有N座房子,第i座房子建在坐标为 的地方,其中住了 人。 松江1843路公交车要在这条路上...

3216
来自专栏小樱的经验随笔

模拟退火算法从原理到实战【基础篇】

  模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达...

3926
来自专栏北京马哥教育

Numpy 隐含的四大陷阱,千万别掉进去了!

陷阱一:数据结构混乱 array 和 matrix 都可以用来表示多维矩阵: ? 看起来效果不错。假设我们要对数据进行筛选,取第 1 列的第 1 行和第 3 ...

4296
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(六)No.57

照例甩一波链接。 大数据计数原理1+0=1这你都不会算(一)No.47 <- HashSet 大数据计数原理1+0=1这你都不会算(二)No.5...

2036

扫码关注云+社区

领取腾讯云代金券