四、硬币找零问题
给你不同面值的硬币和金额总额。写一个函数来计算需要最少数量的硬币。如果钱不能由当前硬币组合,返回-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代码