深入理解动态规划算法 | 凑硬币

动态规划(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的实现思路：

注：上述代码中path变量的理解难度较大，后续文章将深入介绍代码实现。

3. 结语

如果不了解算法思想，不了解分析问题的思路和方法，即使精通任何一门编程语言也无济于事，因为无从下手，这也是公众号一直强调的分享算法思想，帮助大家彻底理解算法。