动态规划算法

1、简介

动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度， 因此它比回溯法、暴力法等要快许多。

现在让我们通过一个例子来了解一下DP的基本原理。


如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候)


就该问题总结一下，随着要凑够钱数的增加：

1.首先要知道所有不大于该钱数的面值，

2.对于每种面值的硬币，求出当选择一个该面值的硬币时所需的硬币数

当选择一个硬币后，所需硬币数+1，所要凑够的钱数=原所要凑的钱数-该硬币面值，所要凑够的钱数减少，求减少后要凑钱数最少所需硬币数，属于原问题的子结构，已求出解

3.在上述求出的结果集中，选择最小值，即为要凑够该钱数所需的最少硬币数

python实现代码：

# 如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元
__author__ = 'ice'


def select_coin(coin_value, total_value):
    min_coin_num = [0]
    for i in range(1, total_value + 1):
        min_coin_num.append(float('inf'))
        for value in coin_value:
            if value <= i and min_coin_num[i - value] + 1 < min_coin_num[i]:
                min_coin_num[i] = min_coin_num[i - value] + 1

    return min_coin_num

sum=int(input())
result = select_coin([1, 3, 5], sum)
print("coin number:" + str(result[-1]))

2、总结

动态规划还是挺难的。
一方面，我们需要把问题状态化，拆分各种子状态，并且将状态用状态方程来表示。
另一方面，即使我们获得状态方程了，用代码的形式来表达的时候，仍然存在一定的转化难题。这需要我们对编程语言的基础比较好，能够想起什么编程方法可以实现这样的功能。

总而言之，动态规划需要的是对问题的分解。

---

参考：
1.动态规划详解