专栏首页爬蜥的学习之旅常见动态规划的解决思路

常见动态规划的解决思路

字符串输入的一般解决思路

  • 选择suffix作为子问题
  • 选择prefix作为子问题
  • 使用子集substring
  • 有时候单个的选择已经不够了,比如背包问题,不仅需要知道要选择哪个物件,来得到价值,同时也需要知道还剩多少容量,也就是需要"记住"更多的子问题,或者说子条件来处理问题

编辑距离

给定两个字串x和y,将x变成y所需要改变的字符的个数是多少?期间可以的操作是:

  • 插入字符c 耗时O(1)
  • 删除字符c 耗时O(1)
  • 将c更新为c' 如果C和C'是相同的,耗时O(0),其它不考虑

字串可以是非连续的。它等效于找两个字符串的最大公共字串,比如 HIEROGLYPHOLOGY 和 MICHAELANGELO 最大公共字串为 HELLO

动态规划思路

  1. 子问题:X的子串X[i:]和Y的子串Y[j:]

  1. 猜测:只有3中可能的方式,要么把X[i]替换成Y[i],要么删掉X[i],要么把Y[i]插入X
  2. 循环:DP(i,j)=min(cost of replace X[i] to Y[j]+ DP(i+1,j+1),cost of delete X[i]+DP(i+1,j),cost of insert Y[j]+DP(i,j+1) )

子问题的耗时:O(1)

  1. 拓扑排序:三个方向由右下角向左下角开始执行
for i in 0,...,|x|:
    for j in 0,...,|y|:
复制代码

原始的问题:DP(0,0),总的时间为:O(1)*O(|x||y|)

矩阵相乘在哪个部分加括号运算才能使得运算最优

假设有如下形式的矩阵做乘法

如果直接按照顺序来计算,先乘A.B,得到的结果再乘C

如果优先运算 B.C ,结果再乘A

可以看到第二种方式消耗的时间会更少。

思路

动态规划解决思路

如何使得词在段落中的位置分配合理,使得更美观

给定一个词的集合words,使用badness(i,j)表示使用的单词是words[i,j]

暴力解决方案

动态规划

按照标准的动态规划步骤来进行:

  1. 找到子问题:集合的后缀 words[i:]

假设找到了第一行的分隔点,那么接下来需要考虑的是第二行又该在哪儿开始换行呢?依次继续往下去查找,所以需要思考的子问题就是去掉第一行的词之后,剩下的那些单词

子问题的数量:n。只有n个单词,后缀的次数也就是这些

  1. 猜测:第二行从哪儿开始?

猜测的选择的数量:<=n-i=O(n)。每次选完了第一行,只需要在剩下的单词里面选

  1. 循环: DP[i]=min(badness(i,j)+DP[j] for j in range(i+1,n+1))

定义问题为求DP(i)的最小值。当i=n的时候,是没有单词剩下的,花销是0。 假设第一次在第i个位置开始换行,第一行的计算发方式为 badness(i,j),剩下的需要解决的问题部分是从i+1开始的单词,也就是剩下部分的花销假设从j开始,它可能取得剩下部分的任意值,每个j的取值所需要的花销就是D(j),那么这两部分相加最小时,也就是最优的划分方式

循环部分耗时(每个子问题耗时):O(n)。j总共有n种选择,加法部分是常量

  1. 拓扑排序:i=n,n-1,...,0

  1. 检验原始问题是否解决:即DP(0)是否解决

使用一个指针parent来表明j中的最小值是那个,那么沿着parent指针,0->parent[0]->parent[parent[0]]一直到最后,即可得到最佳的划分方式

吉他放手指的问题

有一个吉他,在弹的时候,可以用任何一个手指来谈,那么如果给予一系列的音符notes,每个音符都需要用手(手指头取值 1,..,F)处理,每个手指去某个音符弹后需要移到另一个音符用一个手指去弹,假设描述这种移动使用d(p,f,q,g)表示花销,那如何去使得花销最小?

d(p,f,q,g):表示手指f移动到g,弹的音符从p到q

一般思考是:

  1. 子问题:notes[i:],即后面的音符怎么去弹
  2. 猜测:该用那个手指头来谈音符i
  3. 循环:可以选择任意一个手指头去弹新的音符,但是当从旧的音符切换到新的音符去弹的时候,无法知道该切换到那个手指: DP(i)=min(DP(i+1)+d(i,f,i+1,?) for f in 1,..F) 所以子问题"记住"的过少,需要增加考虑的情况。

正确思路为:

  1. 子问题:notes[i:],即后面的音符怎么去弹,同时该那个手指f去弹notes[i:]
  2. 猜测:使用手指g来谈notes[i+1]
  3. 循环: DP(i,f)=min(DP(i+1,g)+d(i,f,i+1,g) for g in 1,..F)

i表示note[i]的音符

  1. 拓扑排序
 for i in reversed(range(n)): //所有的音符
    for f in 1...F: //每个手指头都有可能来弹音符
    
复制代码

最终去解决原始问题,DP(0,f),但是需要指定f,所以使用 min(DP(0,f) for f in 1,...,F),即初始的时候应该选择那一个手指去谈第一个音符

这种场景即是要考虑更多的情况,来达到最优解

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 约束条件变更对算法运行时间所带来的影响

    有1,...,n次请求,去获取单个资源,每个请求的开始时间是s(i),结束时间是f(i), 对于请求i和j,如果二者的区间不重合,即f(i)<=s(j) 或者 ...

    爬蜥
  • 初识Storm

    爬蜥
  • 文本获取和搜索引擎之推荐系统

    推荐系统即把恰当的内容推送给用户,类似于在一系列文档中过滤出用户想要的。一般有两种方式:

    爬蜥
  • Prometheus:pushgateway

    1、安装 2、启动 pushgateway --web.listen-address="0.0.0.0:9091"

    用户5760343
  • 线性代数——(3)矩阵

    羊羽shine
  • dashucoding记录2019.6.7

    购买阿里云ECS主机 购买域名 申请备案 环境配置 安装wordpress 域名解析 在“产品与服务”中选择云服务器ECS

    达达前端
  • 线性代数基础之A的LU分解

    ---- 概述 在线性代数基础之矩阵乘法已经介绍了矩阵乘法的行图像和列图像代表什么什么意义,包括在求解Ax=b的线性方程组是通过消元法来求解该方程组以及矩阵的逆...

    BrianLv
  • 模糊C均值聚类算法(FCM)

    模糊聚类算法是一种基于函数最优方法的聚类算法,使用微积分计算技术求最优代价函数.在基于概率算法的聚类方法中将使用概率密度函数,为此要假定合适的模型.模糊聚类算法...

    AIHGF
  • Matalab之模糊KMeans实现

    转自:http://www.cnblogs.com/zcftech/p/3147062.html

    AIHGF
  • Couchdb命令执行

    风流

扫码关注云+社区

领取腾讯云代金券