动态规划

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

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

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

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

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

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

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

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据处理

tensorflow dropout用法

66540
来自专栏技术随笔

[RNN] Simple LSTM代码实现 & BPTT理论推导

52640
来自专栏利炳根的专栏

学习笔记CB013: TensorFlow、TensorBoard、seq2seq

tensorflow基于图结构深度学习框架,内部通过session实现图和计算内核交互。

47070
来自专栏每日一篇技术文章

OpenGL ES _ 着色器_纹理图像

玩过游戏的同学们,都知道在游戏人物身上穿的那个叫皮肤,专业点将那个就叫做纹理图像。GLSL 支持在顶点和片段着色器使用纹理图像。

23330
来自专栏鸿的学习笔记

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

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

8810
来自专栏zingpLiu

机器学习之线性代数

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

20710
来自专栏机器之心

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

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

50570
来自专栏学习有记

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

11820
来自专栏帮你学MatLab

《Experiment with MATLAB》读书笔记(四)

读书笔记(四) 这是第四部分数组与矩阵 将代码复制到m文件即可运行 函数部分需新建m文件保存 %% 向量与矩阵 x = [2; 4] % ...

387110
来自专栏HansBug's Lab

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

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

52350

扫码关注云+社区

领取腾讯云代金券