动态规划(二)

四、硬币找零问题

给你不同面值的硬币和金额总额。写一个函数来计算需要最少数量的硬币。如果钱不能由当前硬币组合,返回-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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P3165 [CQOI2014]排序机械臂

题目描述 为了把工厂中高低不等的物品按从低到高排好序,工程师发明了一种排序机械臂。它遵循一个简单的排序规则,第一次操作找到摄低的物品的位置P1,并把左起第一个至...

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

cuda中的二分查找

  使用背景 通常,在做高性能计算时,我们需要随机的连接某些点。这些点都具有自己的度量值,显然,度量值越大的值随机到的概率就会越大。因此,采用加权值得方法: v...

1765
来自专栏aCloudDeveloper

算法导论第八章线性时间排序

一、线性时间排序算法历史概览       计数排序首先是由 Harold H. Seward 于1954年提出,而且他还提出将计数排序和基数排序进行结合的思想;...

2076
来自专栏苦逼的码农

从0打卡leetcode之day8--反转整数

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。

1124
来自专栏数据结构与算法

P2709 小B的询问

题目描述 小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求 的值,其中i的值从1到K,其中c(i)表示数字i在...

3307
来自专栏数据结构与算法

洛谷P3807 【模板】卢卡斯定理exgcd

题目背景 这是一道模板题。 题目描述 给定n 求  保证P为prime C表示组合数。 一个测试点内包含多组数据。 输入输出格式 输入格式: 第一行...

3066
来自专栏和蔼的张星的图像处理专栏

28. 搜索二维矩阵二分法

写出一个高效的算法来搜索 m × n矩阵中的值。 这个矩阵具有以下特性: 每行中的整数从左到右是排序的。 每行的第一个数大于上一行的最后一个整数。 样例...

572
来自专栏前端儿

茵茵的第一课

输入第一行是一个整数N(N<10)表示测试数据的组数) 接下来的n行 每行只有一个数(可能是小数,也可能是整数) 这个数的位数(整数位数+小数位数)不超过19位...

1003
来自专栏大数据风控

Python中如何进行数据分组

数据分组 根据数据分析对象的特征,按照一定的数值指标,把数据分析对象划分为不同的区间进行研究,以揭示其内在联系和规律性。 cut 函数: cut(series,...

2487
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(11-15打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

641

扫码关注云+社区