专栏首页算法与编程之美深入理解动态规划算法 - 凑硬币

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

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

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

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

import numpy as npMAX_YUAN = 20# dp表示凑够n元最少需要多少硬币dp = np.zeros((MAX_YUAN,) , dtype=np.int)dp[1] = 1dp[2] = 2dp[3] = 1dp[4] = 2dp[5] = 1# path表示凑够n元第一次选择的币值path = np.zeros((MAX_YUAN,), dtype=np.int)path[0] = 0path[1] = 1path[2] = 1path[3] = 3path[4] = 3path[5] = 5for 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 5i = 19while i != 0: print(path[i]) i = i - path[i]

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

结语

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

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

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

拓展阅读:

深入理解遗传算法(一)

深入理解遗传算法(二)

从1到100求和学算法思维(一)

从1到100求和学算法思维(二)

从1到100求和学算法思维(三)

从1到100求和学算法思维(四)

从1到100求和学算法思维(五)

从1到100求和学算法思维(六)

where2go 团队


微信号:算法与编程之美

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

本文分享自微信公众号 - 算法与编程之美(algo_coding),作者:gongsuochen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    动态规划(Dynamic Programming)算法是计算机科学科学领域中最重要也是最常用的一个算法,巧妙的利用它可以解决很多复杂的问题,而且该算法也频繁的出...

    算法与编程之美
  • Python|一男子竟然用python干这事儿

    游戏,大家一定不陌生,那么有没有想过游戏是怎么做出来的呢?作为一个与代码打交道的人,都知道是用一行一行代码堆积出来的。今天,大家就跟小编一起来用代码敲出一款属于...

    算法与编程之美
  • 深入理解动态规划算法 - 凑整数

    从初中开始我们就接触了函数的概念,所谓函数指的就是给定自变量x,根据某种映射规则进行运算后,会得到一个值y。

    算法与编程之美
  • FAIR 开源 Tensor Comprehensions,让机器学习与数学运算高性能衔接

    AI 研习社消息,Facebook AI 研究院于近日开源了 C++ 库及数学语言 Tensor Comprehensions,它能有效填补研究人员于数学运算领...

    AI研习社
  • 求十个数中最大值和最小值-C++

    汐楓
  • 动态规划中篇:爬楼梯

    主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

    double
  • GitHub 发布10月21日系统故障分析报告

    GitHub 刚刚通过官方博客发布了 21 日“挂掉”的事件分析。GitHub 指出此次事件发生的原因是在 10 月 21 日 22:52 UTC 进行日常维护...

    Debian社区
  • 车道检测--VPGNet: Vanishing Point Guided Network for Lane and Road Marking

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1148525
  • Linux下部署Spring Boot jar

    部署Spring Boot项目可以使用Maven命令mvn:clean package将项目打包成只执行的jar文件,然后使用命令java -jar XX.ja...

    技术从心
  • 世界杯黑马出没,莫斯科没有眼泪

    世界杯来临前,作为公司最资深也是唯一的DBA强哥早就就规划好看球攻略,不曾想今年的世界杯格外得冷。

    腾讯云数据库 TencentDB

扫码关注云+社区

领取腾讯云代金券