动态规划

​ 动态规划一般来说和分治有点类似都是让他们去处理相同的子问题,但是在动态规划里面你会遇到更多的相同子问题。然后我们就会导致很多的重复计算,所以一般我们可以使用递归来完成一个动态规划要完成的任务,但是这样一般会重复计算很多东西,所以动态规划一般就增加了一些矩阵来存放上一次计算的结果。

​ 例如斐波那契数列,这个如果我们直接使用地柜计算的话,我们会很多重复计算。然后当我们要使用一个阵列计算的时候我们在每一次计算之前我们都需要进行一次判断看看我们目前的结果是不是已经被计算了,如果计算了就相当于查表直接获取答案,否则我们才开始计算。

状态:状态就是对于每一个字问题都可以使用一个数字 n 来描述这个子问题,如果状态相同就说明他们的答案相同。

​ 状态也可以有很多维度,例如排列组合就可以使用二维的,距离使用三维的,所谓的维度就是影响这个子问题的因素,也就是上面的那个 n 以及其他自定义的 j 等等!

状态转移方程:就是使用当前的状态来获取其他的状态。

​ 一般状态转移方程可以使用 top down 也可使用 bottom up 方法。

​ 给一个例子:现在有红 绿 蓝 三种颜色的油漆图一面墙,这面墙 红绿 和 绿蓝不能相邻问共有多少中涂色的方法。

​ 状态:定义长度为 n 的时候的涂色的方法数,然后出事值就是当 n 等于 1 的时候涂色的方法就是三种。但是这样我们发现很难写出状态方程,所以我们就再添加一个维度。第二个维度的意思就是颜色。

于是就可以得到这样的状态转移方程。看起来稍微有点复杂。而我们最后求结果就是

另外一个例子就是骨牌的问题,这个问题就是费时数列的问题,但是我们需要自己进行研究开始的几种情况。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

动态规划基本要素

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

20810
来自专栏HansBug's Lab

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

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

3175
来自专栏CVer

TensorFlow从入门到精通 | 01 简单线性模型(上篇)

[TensorFlow从入门到精通] 01 简单线性模型(上)介绍了TensorFlow如何加载MNIST、定义数据维度、TensorFlow图、占位符变量和O...

992
来自专栏小鹏的专栏

身份证识别——生成身份证号和汉字

还是直接代码吧(genIDCard.py),代码中有注释很容易读懂,原理跟验证码识别一样(tf20: CNN—识别字符验证码),都属于定长字符串识别,接下来也...

4399
来自专栏贾老师の博客

启发式寻路算法

4843
来自专栏鸿的学习笔记

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

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

611
来自专栏机器学习原理

深度学习——RNN(3)

2605
来自专栏机器之心

教程 | 在Python和TensorFlow上构建Word2Vec词嵌入模型

选自adventuresinmachinelearning 机器之心编译 参与:李诗萌、刘晓坤 本文详细介绍了 word2vector 模型的模型架构,以及 T...

4637
来自专栏数据处理

tensorflow dropout用法

4584
来自专栏学习有记

2018 蓝桥杯省赛 B 组模拟赛(五)题目及解析

992

扫码关注云+社区