从八卦的递归到动态规划

题外话：

好久没写博客了，主要觉得自己写的不怎么样，肚子没墨水了。今天又出来榨干肚子里的最后一滴墨水。

进入正题：

前面写过两篇动态规划的题目，今天又遇到动态规划了，想到了一个更容易理解的方法，我们用凑硬币这道题目来加深理解。网络上这个题目已经被写烂了，大多数文章都是复制粘贴的。本文原创。开始讲解之前读者需要了解递归。本文从递归解法讲起直到推出动态规划方法。

问题描述：

（凑硬币问题）给你 k 种面值的硬币，面值分别为 c1, c2 ... ck ，每种硬币的数量无限，
再给一个总金额 amount ，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回-1
这里我们k = 3 , c1 = 1、c2 = 3、c3 = 5.

1. 递归解法：

形象的理解递归：
比如f是一个八卦的人，有一天a和b谈恋爱了，只告诉了c。 f想知道a和b的关系， 就去问e， e说他自己不知道可以帮忙去问d，d说他也不知道可以帮忙去问c（递归调用过程），c呢就告诉了d，d又告诉了e，e告诉了f（回溯过程，回溯过程可以看作答案一步步传到f耳朵里的过程）。
用递归的思想来思考该问题大致如下：
我们知道amount=0和amount<0基本情况（c知道a和b的关系），求amount=11的答案（f想知道a和b的关系），ans(11)=ans（11-5）+1 or ans(11)= ans(11-3)+1 or ans(11)= ans(11-1)+1 （f去问了他认识的人e。如果f认识d或者直接认识c他可以更快的知道答案）。递归的回溯过程程序会自动完成。

def colCoins_rec(coins, amount):
    """
    递归解法
    :param coins: 硬币面值
    :param amount: 总金额
    :return: 凑齐总金额的最少硬币数量
    """
    # 基本情况（c知道的情况）
    if amount == 0:
        return 0
    if amount < 0:
        return -1
    
    res = float("inf")
    # 有三种面值的硬币可以选择（f认识的人，因为f只认识e所以只有一个选择）
    for coin in coins:
        #选择（f选择问谁，交给谁来获取答案）
        subproblem = colCoins_rec(coins, amount-coin)
        # 子问题无解，（f问到了错误地人g，g是个孤儿谁都不认识，走到了死胡同，f要问下一个人）
        if subproblem < 0: continue
        # 选择最优的答案（如果f认识c，那么他很快可以获取答案，就可以选择这条信息链）
        res = min(res, 1+colCoins_rec(coins, amount-coin))
    return res

递归方法存在什么问题呢？很明显的一个是使用了函数调用栈，栈在计算机中是一个相对很有限的资源。还有一个是存在重叠子问题，导致了时间复杂度大大增加。LeetCode上这个方法一般是无法通过的。重叠子问题是什么呢？

                    h                  存在直接连线的表示互相认识
                 /     \               如果h想从c那里获得c知道的答案那么他要问认识的f，g同样
                f       g               f，g要问他们认识的人。
              /  \    /  \            观察发现f，e，g被问了多次！这是导致算法复杂度高的主要原因
            g    e   e   f
          /  \   ........
        e     f
      /  \
    c    d

如何解决上述存在的重叠子问题呢？答案是使用备忘录方法。

2备忘录递归方法

备忘录方法是这些人共用一个列表的，如果谁已经知道答案就填在列表对应的元素里里，每个人在问之前先访问列表，如果得到大难就不用再继续问下去了，避免重复的被问。

mem = [-1]*15
def colCoins_rec_mem(coins, amount, mem):
    """
    在递归的解法的基础上加上备忘录解决重叠子问题。
    :param coins: 硬币面值
    :param amount: 总金额
    :param mem: 备忘录
    :return: 最少硬币数量
    """
    # 基本情况（c知道的答案）
    if amount < 0:
        return -1
    if amount == 0:
        return 0
    # 查看备忘录，看看是否计算过（是否被问过）
    if mem[amount] != -1:
        return mem[amount]
    # 选择（询问的过程）
    res = float("inf")
    for coin in coins:
        subproblem = colCoins_rec_mem(coins, amount-coin, mem)
        if subproblem < 0: continue
        res = min(res, 1+colCoins_rec_mem(coins, amount-coin, mem))
        # 得到答案后写进备忘录
        mem[amount] = res
    return res

我们可以看到基于备忘录的递归算法，会在计算（询问）前去查看备忘录，避免重复计算。而且代码与纯递归方法也非常的相似。只多了查看备忘录的过程和获得答案后写进备忘录的操作。这个备忘录解决了重叠子问题，实际上他还是递归方法。我们可以看到其实备忘录记录的就是子问题和原问题的答案，递归方法是自顶向下的以“询问”的方法求得答案，那么可不可以让c主动的向他认识的人扩散答案直到让f知道答案。这个自底向上的“传播”就是动态规划！（好烦c这种人啊，就像我很烦动态规划题目）话不多说看代码

def colCoins_mem(coins, amount):
    """
    自底向上递推出答案
    :param coins:  硬币面值
    :param amount: 总金额
    :return:
    """
    # 构造一个备忘录
    mem = [0]*(amount+1)  # mem[i]表示凑出金额i需要的最少硬币的数量
    # 基本情况（这句代码可以不要）
    mem[0] = 0
    # 开始推导（c开始传播八卦了）
    for i in range(1, amount+1):
        # 从c开始向他认识的人传播消息
        for coin in coins:
            res = i - coin
            if res >= 0:
                mem[i] = mem[res] + 1
            else:
                continue
    return mem[amount]

总结：

我们看看动态规划的要素就是：1、基本情况（知道答案的那个人）2、明确mem里面存储的是什么我们也可以称作状态。3、选择（每个状态有多少转移方方式）4、明确状态转移的细节（状态转移方程）。该文章一气呵成有什么不懂的留言，有空改一下。动态规划就到这里了。