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

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

动态规划(Dynamic Programming)算法是计算机科学科学领域中最重要也是最常用的一个算法，巧妙的利用它可以解决很多复杂的问题，而且该算法也频繁的出现在各大互联网公司的面试中，因此掌握它是十分必要的。

但该算法对于初学者来说 理解并 掌握并非易事，本系列教程将带领大家一起来学习该算法，通过经典的案列介绍和问题分析以及 python 代码实现，帮助大家彻底理解动态规划。

问题描述

首先我们来看一道非常经典的“凑硬币”题目：

面值为 1 元、 3 元、 5 元的硬币若干，如何用最少的硬币凑够 11 元？

解决方案

在具体的编码之前，需要对问题做深入的分析。

步骤 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变量的理解难度较大，后续文章将深入介绍代码实现。

结语

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

后面将持续分享 深入理解 计算机领域经典算法的文章，欢迎持续关注。

如果您对某些算法有困惑，欢迎下方留言，我们将第一时间为大家提供博客阐述算法思想。

拓展阅读：

深入理解遗传算法(一)

深入理解遗传算法(二)

从1到100求和学算法思维（一）

从1到100求和学算法思维（二）

从1到100求和学算法思维（三）

从1到100求和学算法思维（四）

从1到100求和学算法思维（五）

从1到100求和学算法思维（六）

where2 go 团队

微信号：算法与编程之美

长按识别二维码关注我们!

温馨提示： 点击页面右下角 “写留言” 发表评论，期待您的参与！期待您的转发！