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