专栏首页AI那点小事关于动态规划

关于动态规划

递归到动规的一般转化方法

    递归函数有n个参数,就定义一个n维的数组,数组的下标是递归函数参数的取值范围,数组元素的值是递归函数的返回值,这样就可以从边界值开始,逐步填充数组,相当于计算递归函数值的逆过程。                                                                                                                        

动规解题的一般思路

  1. 将原问题分解为子问题 1) 把原问题分解为若干个子问题,子问题和原问题形式相同或类似,只不过规模变小了。子问题都解决,原问题即解决(数字三角形例)。 2)子问题的解一旦求出就会被保存,所以每个子问题只需求解一次。
  2. 确定状态 所有“状态”的集合,构成问题的“状态空间”。“状态间”大小,与用动态规划解决问题的时间复杂度直接相关。在数字三角形的例子里,一共有N×(N+1)/2个数字,所以这个问题的状态空间里一共就有N×(N+1)/2个状态。整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。 在数字三角形里每个“状态”只需要经过一次,且在每个状态上作计算所花的时间都是和N无关的常数。 用动态规划解题,经常碰到的情况是,K个整型变量能构成一个状态(如数字三角形中的行号和列号这两个变量构成“状态”)。如果这K个整型变量的取值范围分别是N1, N2, ……Nk,那么,我们就可以用一个K维的数组array[N1] [N2]……[Nk]来存储各个状态的“值”。这个“值”未必就是一个整数或浮点数,可能是需要一个结构才能表示的,那么array就可以是一个结构数组。一个“状态”下的“值”通常会是一个或多个子问题的解。
  3. 确定一些初始状态(边界状态)的值 以“数字三角形”为例,初始状态就是底边数字,值就是底边数字值。
  4. 确定状态转移方程 定义出什么是“状态”,以及在该 “状态”下的“值”后,就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的“状态”,求出另一个“状态”的“值”(“人人为我”递推型)。状态的迁移可以用递推公式表示,此递推公式也可被称作“状态转移方程”。数字三角形的状态转移方程:

能用动规解决的问题的特点

    1) 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质。
    2) 无后效性。当前的若干个状态值一旦确定,则此后过程的演变就只和这若干个状态的值有关,和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态,没有关系。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2017美国数学建模MCM A题(连续型)翻译 管理赞比西河

    The Kariba Dam on the Zambezi River is one of the larger dams in Africa. Its con...

    AI那点小事
  • 首个重复字符

    题目描述 对于一个字符串,请设计一个高效算法,找到第一次重复出现的字符。 给定一个字符串(不一定全为字母)A及它的长度n。请返回第一个重复出现的字符。保...

    AI那点小事
  • 历届试题 蚂蚁感冒

    问题描述   长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左,有的朝右。

    AI那点小事
  • 设计模式~状态模式

    状态模式(State Pattern),又称状态对象模式(Pattern of Objects for States),状态模式是对象的行为模式。

    Vincent-yuan
  • 设计模式 ☞ 行为型之状态模式

      状态(State)模式的定义:对有状态的对象,把复杂的“判断逻辑”提取到不同的状态对象中,允许状态对象在其内部状态发生改变时改变其行为。在软件开发过程中,应...

    Demo_Null
  • 研究全脑神经网络时间动态的工具:脑电微状态介绍

    瑞士研究者Christoph M.Michel 和ThomasKoenig在NeuroImage发文,介绍了一种用多通道EEG表征人脑静息态活动的办法。...

    用户1279583
  • java设计模式之状态模式,策略模式的孪生兄弟

    状态模式(State Pattern)中,类的行为是基于它的状态改变的,状态之间的切换,在状态A执行完毕后自己控制状态指向状态B,状态模式是不停的切换状态执行,...

    用户4361942
  • 【每日算法Day 61】LeetCode 672. 灯泡开关 Ⅱ

    现有一个房间,墙上挂有 只已经打开的灯泡和 个按钮。在进行了 次未知操作后,你需要返回这 只灯泡可能有多少种不同的状态。

    godweiyang
  • 设计模式之状态模式(行为型)

    一个对象在其内部状态改变时改变其行为,这个对象我们可以称为状态对象,所以状态模式是一种对象行为型模式。

    SmileNicky
  • Flink 状态管理与 Checkpoint 机制

    相对于其他流计算框架,Flink 一个比较重要的特性就是其支持有状态计算。即你可以将中间的计算结果进行保存,并提供给后续的计算使用:

    zhisheng

扫码关注云+社区

领取腾讯云代金券