动态规划基本要素

动态规划性质: 1  最优子结构性质  2 子问题重叠性质 ----->该问题可用动态规划算法求解的基本要素

1 最优子结构

当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。最优子结构性质提供了该问题的可用动态规划算法求解的重要线索。

动态规划,利用问题的最优子结构性质,以自底向上的方式递归的从子问题的最优解逐步构造出整个问题的最优解。

2 重叠子问题

动态规划,避开了递归时,重复的计算相同子问题的过程,对每个子问题只解一次,而后将其保存在一个表格中,当再次需要的时候,只是简单的用常数时间查看一下结果。

3 备忘录方法

递归方式自顶向下

首先,查看其相应的记录项,若存在,直接返回。若不存在,则保存,以备以后继续查看。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

算法模板——线段树6(二维线段树:区域加法+区域求和)(求助phile)

实现功能——对于一个N×M的方格,1:输入一个区域,将此区域全部值作加法;2:输入一个区域,求此区域全部值的和 其实和一维线段树同理,只是不知道为什么速度比想象...

3175
来自专栏zingpLiu

机器学习之线性代数

  完整内容已上传到github:https://github.com/ZingP/machine-learning/tree/master/linear_al...

1711
来自专栏有趣的Python

7- 深度学习之神经网络核心原理与算法-模型的保存与加载

1545
来自专栏祥子的故事

tensorflow | 重新学习 | 了解graph 和 Session

3648
来自专栏ATYUN订阅号

四个用于Keras的很棒的操作(含代码)

Keras是最广泛使用的深度学习框架之一。它在易于使用的同时,在性能方面也与TensorFlow,Caffe和MXNet等更复杂的库相当。除非你的应用程序需要一...

1264
来自专栏漫漫深度学习路

tensorflow学习笔记(三十):tf.gradients 与 tf.stop_gradient() 与 高阶导数

gradient tensorflow中有一个计算梯度的函数tf.gradients(ys, xs),要注意的是,xs中的x必须要与ys相关,不相关的话,会报错...

1.4K9
来自专栏mwangblog

开始使用Octave

1904
来自专栏深度学习之tensorflow实战篇

tensorflow之tf.placeholder 与 tf.Variable区别对比

二者的主要区别在于 Variable:主要是用于训练变量之类的。比如我们经常使用的网络权重,偏置。 值得注意的是Variable在声明是必须赋予初始值。在训...

3294
来自专栏鸿的学习笔记

写给开发者的机器学习指南(十三)

在我们实际使用支持向量机(SVM)之前,我先简要介绍一下SVM是什么。 基本SVM是一个二元分类器,它通过选取代表数据点之间最大间隔的超平面将数据集分成2部分。...

611
来自专栏Java 源码分析

动态规划

​ 动态规划一般来说和分治有点类似都是让他们去处理相同的子问题,但是在动态规划里面你会遇到更多的相同子问题。然后我们就会导致很多的重复计算,所以一般我们可...

3005

扫码关注云+社区