力扣0322-零钱兑换

问题

给定不同面额的硬币(coins)和一个总金额(amount) 。写一个函数来计算可以凑成总金额所需的最少的硬币个数，如果没有任何一种硬币组合能满足，返回 -1。

示例1

1 2	输入：coins = [1, 2, 5], amount = 11 输出：3 (5+5+1)

示例2

1 2	输入：coins = [2], amount = 3 输出：-1 (无法满足)

核心在于应用动态规划思想，有递归和非递归连个版本的实现方案。

用动态规划和递归的实现版本：

def coins(coinL,Sum):
    if Sum < min(coinL):
        return -1
    else:
        if Sum in coinL:
            return 1
    minNum = None
    for coin in coinL:
        coinret = coins(coinL, Sum-coin)
        if coinret > 0: # 无解的情况的直接忽略
            if minNum is None:
                minNum = coinret
            else:
                if minNum > coinret:
                    minNum = coinret
    if minNum is None:
        return -1
    else:
        return 1+minNum

想进一步将上述递归该成尾递归，进而去掉尾递归以提高效率，却发现不容易做。通过对比猜测原因：回溯法（如智能体版本的八皇后）实现的递归，比较容易改成尾递归；或者无分叉的递归（如阶乘），也容易修改成尾递归版本。然而零钱兑换既有分叉，又不好用回溯，因此不容易用尾递归实现。

虽然不容易通过尾递归这条路线摆脱递归，但可以通过从底层到高层构建状态集合来摆脱递归。

用了动态规划思想，但没用递归而是用循环。令num=states[sum]表示sum金额的最小硬币数是num，作为一个状态。sum较小的状态定义为小状态，sum越大则状态越大。不用递归的话，只能先构建小的状态，在小状态基础上构建大状态，直到构建到题目要求的状态Sum为止。

def coins(coinL,Sum):
    if Sum < min(coinL):
        return -1
    states = {}
    for coin in coinL:
        states[coin] = 1
    for s in range(1,Sum+1):
        if s not in states.keys():
            minNum = None
            for coin in coinL:
                if s-coin in states.keys():
                    if minNum is None:
                        minNum = states[s-coin]+1
                    else:
                        if minNum > states[s-coin]+1:
                            minNum = states[s-coin]+1
            if minNum is not None:
                states[s] = minNum
    if Sum in states.keys():
        return states[Sum]
    else:
        return -1

12输入：coins = [2], amount = 3输出：-1 (无法满足)

1
2
输入：coins = [2], amount = 3
输出：-1 (无法满足)