python实现找钱动态规划算法

### 回答1：
找钱问题是一个经典的动态规划问题，它的目标是找到一种最优的方式，用最少的货币数量找回一定数额的零钱。这个问题可以用动态规划算法来解决。

具体实现过程如下：

1. 定义问题的状态

首先定义问题的状态。对于找钱问题，我们可以定义状态为：对于金额为i，需要找回的最少货币数量为d(i)。

2. 状态转移方程

接下来，我们需要定义状态转移方程。假设有一组货币面值集合S={c1, c2, c3, ..., cm}，对于金额i，我们可以枚举所有的面值，然后找到一个最小值，即：

d(i) = min{d(i-ci)+1} (ci∈S)

其中，d(i-ci)表示金额为i-ci时的最少货币数量，加1表示再加上面值为ci的一张货币。

3. 初始化状态

对于金额为0时，需要找回的最少货币数量为0，即d(0)=0。

4. 计算最终结果

最终结果即为d(n)，其中n为需要找回的金额。

下面是具体的Python代码实现：

def find_min_coins(n, coins):
    # 初始化状态
    d = [float('inf')]*(n+1)
    d[0] = 0

    # 计算状态转移方程
    for i in range(1, n+1):
        for coin in coins:
            if i >= coin:
                d[i] = min(d[i], d[i-coin]+1)

    # 返回最终结果
    return d[n]

其中，n为需要找回的金额，coins为货币面值的集合。

例如，如果需要找回15元钱，可以用1元、5元、10元、20元纸币进行找零，可以调用如下代码：

coins = [1, 5, 10, 20]
n = 15
result = find_min_coins(n, coins)
print(result)  # 输出结果为2，即需要2个5元硬币

以上就是Python实现找钱动态规划算法的过程。

### 回答2：
找钱动态规划算法的实现步骤如下：

1. 创建一个长度为amount+1的数组dp，并将其初始化为无穷大。
2. 设置dp[0] = 0，因为找零钱数为0时不需要任何硬币。
3. 循环遍历硬币的面值，对于每一个硬币面值coin，从coin到amount的范围内更新dp数组。
a. 对于每一个金额j，如果dp[j-coin]不是无穷大且dp[j-coin]+1 < dp[j]，则更新dp[j] = dp[j-coin] + 1。
b. 目的是找到组成金额j所需的最少硬币数量。
4. 返回dp[amount]，即组成金额amount所需的最少硬币数量。

动态规划的思路是从小到大地计算组成不同金额所需的最少硬币数量。
通过不断更新dp数组，可以找到组成amount所需的最少硬币数量。

以下是对于输入金额amount = 11和硬币面值coins = [1, 2, 5]的Python代码示例：

def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0

for coin in coins:
for j in range(coin, amount+1):
if dp[j-coin] != float('inf') and dp[j-coin] + 1 < dp[j]:
dp[j] = dp[j-coin] + 1

return dp[amount]

coins = [1, 2, 5]
amount = 11
result = coinChange(coins, amount)
print(result)

输出结果为3，表明组成金额11需要用到3个硬币。