动态规划(Dynamic Programming)算法是计算机科学科学领域中最重要也是最常用的一个算法，巧妙的利用它可以解决很多复杂的问题，而且该算法也频繁的出现在各大互联网公司的面试中，因此掌握它是十分必要的。
但该算法对于初学者来说理解并掌握并非易事，本系列教程将带领大家一起来学习该算法，通过经典的案列介绍和问题分析以及python代码实现，帮助大家彻底理解动态规划。
1. 问题描述
首先来看一道非常经典的“凑硬币”题目：
面值为1元、3元、5元的硬币若干，如何用最少的硬币凑够11元？
2. 问题分析
在具体的编码之前，需要对问题做深入的分析。
步骤1：用函数的形式来表示题目结果。
设f(x)= y，该函数表示凑够x元，最少的硬币数量为y。
举例如下：
- 凑够1元最少的硬币数量为1，则可表示为f(1)= 1
- 凑够11元最少的硬币数量为3，则可表示为f(11)= 3
步骤2：分析递推情况。
凑够11元，我们需要多次选择，如：
第一次选择1元，则还需要凑够11- 1 = 10元；
第二次选择3元，则还需要凑够10- 3 = 7元；
。。。
如果选择了一枚1元硬币，则f(11)= 1 + f(11-1)，表示凑够11元选择了一枚1元硬币，那么还剩下需要凑够11-1= 10元的硬币数量f(10)。
同理如果选择3元则f(11)= 1 + f(11-3)，如果选择5元则f(11)= 1 + f(11-5)。
根据题目要求凑够11元使用最少的硬币，所以
f(11) = min{1+f(10), 1+f(8),1+f(6)}
注：此处大家要充分理解f(x)函数的含义，f(x)表示凑够x元最少需要的硬币数量。
通过分析f(11)我们知道要想求解f(11)必须先求解f(10),f(8), f(6)。
f(10) = min{1+f(10-1), 1+f(10-3), 1+f(10-5)}
f(8) = min{1+f(8-1), 1+f(8-3), 1+f(8-5)}
f(6) = min{1+f(6-1), 1+f(6-3), 1+f(6-5)}
。。。
故，要想求解f(11)，必须先求解f(10),f(8),f(6)，而要求解f(10)必须先求解f(9),f(7), f(5)，其他的同理，所以只有计算了前面函数的值后，才能得到后面的函数结果。
在认真分析f(11)之后，我们很容易的得出一般情况即：
f(i) = min{ 1+f(i-1), 1+f(i-3), 1+f(i-5)}
凑够i元，可以有三种方案，分别是选择一枚1元、一枚3元或一枚5元，然后选择这三种方案中最小的值。这就是得出的针对一般情况的递推结果。这个递推公式对于求解动态规划题目来说显得尤为重要。
以上就是分析递推的情况，不知您理解了与否。
步骤3：算法实现。
在了解问题的解决思路后，可以选择任何一门熟悉的编程语言去实现，如c,java等。下面将介绍python的实现思路：
import numpy as np MAX_YUAN = 20 # dp表示凑够n元最少需要多少硬币 dp = np.zeros((MAX_YUAN,) , dtype=np.int) dp[1] = 1 dp[2] = 2 dp[3] = 1 dp[4] = 2 dp[5] = 1 # path表示凑够n元第一次选择的币值 path = np.zeros((MAX_YUAN,), dtype=np.int) path[0] = 0 path[1] = 1 path[2] = 1 path[3] = 3 path[4] = 3 path[5] = 5 for i in range(6, MAX_YUAN): candidate = np.zeros((3,), dtype=np.int64) candidate[0] = 1 + dp[i - 1] candidate[1] = 1 + dp[i - 3] candidate[2] = 1 + dp[i - 5] index = candidate.argmin() if index == 0: path[i] = 1 elif index == 1: path[i] = 3 else: path[i] = 5 dp[i] = candidate.min() print(dp) print(path) # 打印凑够19元的硬币币值 # 结果：1 3 5 5 5 i = 19 while i != 0: print(path[i]) i = i - path[i] |
注：上述代码中path变量的理解难度较大，后续文章将深入介绍代码实现。
3. 结语
如果不了解算法思想，不了解分析问题的思路和方法，即使精通任何一门编程语言也无济于事，因为无从下手，这也是公众号一直强调的分享算法思想，帮助大家彻底理解算法。
