动态规划(二)

四、硬币找零问题

给你不同面值的硬币和金额总额。写一个函数来计算需要最少数量的硬币。如果钱不能由当前硬币组合,返回-1

我们首先提炼这个问题的特征,①硬币可重复多次使用,②对于每一枚硬币,都有两种决策,选或者不选。那么我们先试着把暴力代码写出来

图4-1找零暴力代码

这里有两个注意点,第一,某种硬币可以无限拿,这种方式如何表示?其实只要在你选择这个硬币之后,idx不加1,这样下次就还是拿这种硬币。第二,无法找零的情况,要返回-1,但是我们这里有加1,可能导致最后输出的值不是-1,而我们要求的是使用最少的硬币数量,那我们干脆定义一个最大的值maxvalue,然后在主函数中进行if判断,见下图

图4-2主函数

下面直接写出DP代码,记忆化存储值就行了,没什么好说的,一样的套路

图4-3硬币DP代码

五、编辑距离

给定两个字符串S和T,对于T我们允许三种操作:在任意位置添加任意字符、删除存在的任意字符、修改任意字符,问最少操作多少次可以把字符串T变成S

这题稍微有点难度,分析也会比较多,一定认真看,直接复制代码运行了并不代表你会了

先设A的长度为LA,B的长度为LB,并且第一个字符的编号为0。见了这么多题,DP问题大部分都是以首尾作为突破口。首先看一下A[0],由于B最后要变成跟A一样,所以B需要获得一个字符跟A[0]配对,必然满足一种情况:(1)插入一个字符x(x==A[0])到B里面去A[0]配对,(2)使用B本身就有的某个字符B[k](B[k]==A[0])来跟A[0]配对

先说情况一,我们插入一个x(x==A[0])到B里面去。显然x最简单的方法是插入到B[0]的前面,然后将B[1……LB]和A[2……LA]变成一样,但是,除了插入到B的最前面,还可以插入到B的其他位置,当然这个问题是多余的,插到哪里都不会影响最优解,下面给出证明:

假设存在一个最优方案是把x插到B[0]后面的某个位置,譬如说插入到B[2]的前面(B[1]的后面),那么现在我们要做的就是把B[0]和B[1]删掉,然后将B[3……LB]和A[2……LA]变成一样,仔细想想,这不就和我插入最前面一样的吗,所以肯定不会错过最优解!

情况二:要么用B[0]跟A[0]配对,要么不用B[0]。如果我们用B[0]跟A[0]配对:(1)B[0]等于A[0],不需要修改B[0]。(2)B[0]不等于A[0],修改B[0]为A[0]。如果我们不用B[0]跟A[0]配对,意味着B[0]必须被删掉

总结一下,就是下面这张图

图5-1递归式1

其实这个题目有一个比较数学的递归式

图5-2递归式2

其实都是一样的,只不过这个是从后往前考虑,而且读者应该能发现,这道题的递归式跟LCS这题非常相似

图5-3编辑距离DP代码

六、最长公共子序列(LCS)

给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列,现在要求Z最长

首先需要科普一下,最长公共子序列(LCS)和最长公共子串不是一回事。什么子序列呢?就是将给定序列中零个或多个元素去掉之后得到的结果。什么是子串呢?给定子串中任意个连续的字符组成的子序列称为该串的子串

图6-1示例

结合上图,我们分析一下:

假如s1的最后一个元素与s2的最后一个元素相等,那么s1和s2的LCS就等于:(s1减去最后一个元素)与(s2减去最后一个元素)的LCS再加上s1和s2相等的最后一个元素

假如s1的最后一个元素与s2的最后一个元素不等(上图就是这样),那么s1和s2的LCS就等于:(s1减去最后一个元素)与(s2)的LCS,(s2减去最后一个元素)与(s1)的LCS中较大的那一个

递归公式:

图6-2递归公式

都说到这里了,下面酒吧暴力代码写出来吧

图6-3 LCS暴力代码

图6-4 LCS DP代码

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5866
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1152
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1272
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2478
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

761
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2169
来自专栏WOLFRAM

向日葵中的数学之美

1823
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2818
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1786

扫码关注云+社区