动态规划初步

凑钱问题: 题目:给一个总额amount,以及现有的钱币面值数组coins,要求计算最少需要多少张coins中的钱币才能凑出总额;

动态规划是将大问题转化为小问题,然后一步步求解出最终结果。具体到这道题,我们可以把大问题即凑amount元转化为凑齐amout-1,amount-2等等

当我们计算"凑5元"的时候一定要相信:凑1-4元都已经是最优结果了,同样凑4元要相信凑1-3是最优结果。这便是动态规划的全部:大问题转化为小问题,每次小问题都是最优结果,最终基于这些小问题得到大问题的最优结果,各种dp问题的主要不同是大问题是如何“基于小问题”得出结果的

回到上面的图片中,我们这道题目要求的是计算凑amount所需最少的钱币张数,那凑X元储存的就应该是钱币的张数,所以上面的图片进一步转化

当我们凑5元的时候,由于有3中面值可选,我们不确定选哪个是最佳,所以需要遍历一次。当选面值1RMB时,需要借助子问题凑4元的答案;当选面值2RMB时,需要借助子问题凑3元;选面值3RMB需要借助子问题凑2元,如此得出三个答案(A,B,C),最终计算着三个答案哪个是最优结果,即哪个所需张数最少,并将至存放到dp[5]作为凑5元的最优结果,以上便是动态规划在凑硬币问题上的应用,其实既然都叫思想了很明显凡是大问题依赖小问题解的都可以使用dp求出。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

ICML2018论文公布!一文了解机器学习最新热议论文和研究热点

2981
来自专栏AI研习社

Hopfield 网络和玻尔兹曼机!深度学习之父 Geoffrey Hinton 的神经网络第 11 课(中文字幕)

作为深度学习祖师,Geoffrey Hinton 的每一句每一言,都使学习者如奉纶音。浓缩其毕生所学的《Neutral Network for Machine ...

3615
来自专栏LET

glTF(二):PBR

3886
来自专栏量子位

如何用卷积神经网络从歌曲中提取纯人声?这里有教程+代码

安妮 编译整理自 Madebyollin博客 量子位 报道 | 公众号 QbitAI 你应该对阿卡贝拉(Acapella)不陌生吧。这种无伴奏合唱的纯音乐起源于...

4897
来自专栏CVPy

OpenCV玩九宫格数独:预告篇

在刚刚接触机器视觉的时候,我就想着用机器视觉来解数独。当时也做了一些尝试。但是当时只是做到了提取每一个九宫格和数字,由于当时初学能力有限,就搁置了。最近重新拾起...

6620
来自专栏华章科技

一位数学专业女生大学毕业前的感慨:不好意思,是我天真了

问自己永远有多远!!!! 已知X是非平方数,证明X开根号是无理数 TM这还需要证明 学完定与不定积分后

751
来自专栏量化投资与机器学习

【Python量化投资】基于网格优化、遗传算法对CTA策略进行参数优化

投资策略 基于指数移动平均线的交易系统 多头开仓条件:短期均线上穿长期均线同时长期均线大于更长期均线的值 空头开仓条件:短期均线下穿长期均线同时长期均线小于更长...

4688
来自专栏数据结构与算法

洛谷P2158 [SDOI2008]仪仗队

题目描述 作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线...

32310
来自专栏WOLFRAM

月球相当于北京的几环?

2392
来自专栏智能算法

细数 20 世纪最伟大的十大算法

英文:Barry A. Cipra 译者:JULY 链接:blog.csdn.net/v_july_v/article/details/6127953 发明...

35910

扫码关注云+社区

领取腾讯云代金券