这周写题的时候遇到了一个没有了解到的新算法--动态规划，所以之后便去学习了一下，下面我来介绍一下刚学的动态规划算法。

        动态规划是一种用于解决复杂优化问题的算法思想，核心在于将大问题分解为互相关联的子问题，并通过计算子问题的解来避免重复计算，从而高效得到原问题的最优解。

        大概可以分为五步来解决问题：1.确定问题参数 2.定义状态数组 3.初始化边界条件 4.推导状态转移方程 5.获取最终结果。

        下面是一道典型例题作为示例来讲解动态规划思想该如何应用

        你有三种硬币，分别面值2元、5元和7元，每种硬币都有足够多，买一本书需要27元，如何用最少的硬币组合起来正好付清，不需要对方找钱

        首先，确定问题参数，

在这里就是我们要求的最少硬币数量，

虽然我们现在不确定最优组合是什么，但是可以设最少需要k枚硬币，a1a2一直到ak枚硬币，加起来面值为27元。

当然一定就存在最后一枚硬币为ak，那除去ak前面的硬币面值和为27-ak。现在问题从最少多少枚硬币拼出27，变成了最少多少枚硬币拼成了27-ak。

然后确定状态方程

我们可以设  f（x）=i，i就是最少拼出面值和为x的硬币数，对于x

𝑓[𝑥]=𝑚𝑖𝑛⁡{𝑓[𝑥−2]+1,𝑓[𝑥−5]+1,𝑓[𝑥−7]+1}

初始条件和边界情况

 转移方程有两个两个问题：x-2，x-5，x-7小于0怎么办？和什么时候停止运算？

首先第一个问题就是要拼的数（y）为负数或者是一个根本拼不出来的数，比如1，那么就定义f（y）为正无穷，表示拼不出来，然后将初始条件设为f[0]=0

计算顺序

拼出x所需要的最少硬币数：𝑓[𝑥]=𝑚𝑖𝑛⁡{𝑓[𝑥−2]+1,𝑓[𝑥−5]+1,𝑓[𝑥−7]+1}

初始从f[0]=0开始，然后计算f[1]f[2]一直到f[x]

这样当算到x的时候， f[x-2] ,f[x-5] ,f[x-7]都已经算过了

每一步都是算三次，算到27是第27步，故时间复杂度是27*3，远远小于用递归方法的时间复杂度

下面是完整代码示例：

def coinChange(n):

    """

    用于计算找零的最少硬币数。

    参数n：要找零的金额

    返回值：最少硬币数量，如果无法找零，则返回-1

    """

    dp = [float('inf')] * (n + 1)  # 初始化动态规划数组

    dp[0] = 0  # 找零金额为 0 时，需要 0 枚硬币

    for i in range(1, n + 1):

        if i >= 2:

            dp[i] = min(dp[i], dp[i - 2] + 1)

        if i >= 5:

            dp[i] = min(dp[i], dp[i - 5] + 1)

        if i >= 7:

            dp[i] = min(dp[i], dp[i - 7] + 1)

    if dp[n] != float('inf'):

        return dp[n]

    else:

        return -1

n=int(input('请输入要拼的金额：'))

res=coinChange(n)

print(res)