系列历史文章：
算法系列-动态规划(1)：初识动态规划
算法系列-动态规划(2)：切割钢材问题
算法系列-动态规划(3)：找零钱、走方格问题
找零钱问题，凑数问题最近老币越来越值钱，是投资的一个好方向。
这不，八哥从某鱼入手了几张老币。
这是一块的：
这是五块的：
这是十块的：
不得不说，老币还是挺好看的
看看这成色，过几年一定很值钱，这就是我留给我孩子的财产。
但是不小心给罗拉看到了，然后就有了下面的对话....
对话记录罗拉
八哥，这钱不错，给几张给我玩玩八哥
姐姐，这是钱，我的投资，怎么能随便玩
罗拉
我就玩两天，又不会弄坏八哥
这有啥好玩？你又不是没见过
罗拉
真小气,玩下能少块肉？八哥
话是这么说没错，可是我还没捂热呢~
这样吧，虽然我的也是你的，但是你总要付出点啥吧，不然我纯亏
罗拉
怎么？要我买？瞧你这出息...八哥
别激动，这哪能啊，谈钱多伤感情
我用这钱出道题，你答得出来，这钱归你了
答不出来，就让我再捂几天，怎样？
罗拉
行，没问题，但是不能超出我能力范围八哥
这...,好吧
os:岂不是注定我血亏？？？
找零钱的方式
钱？她能力范围？又不太简单？动态规划？八哥脑子一动，马上就想到一个题目。
于是，虎躯一震，眉头一舒，摸摸下巴，点点头。
“有了，罗拉请听题”
“你看，我这里的旧币有面值{1,5,10}的，假设我这里每种币值数量都无限，请问我如果要凑成10元有几种方法？”
“就这？”罗拉听罢，不屑道。
“别急，这只是最简单问题，后面还有几个呢，保证一系列问题。”八哥一副奸计得逞的嘴脸。
“行吧，这有何难，组成十元，有以下几种。”罗拉自信满满。
“第一种：我用10张一元”；
“第二种：我用2张五元”；
“第三种：我用1张十元”；
“第四种：我用1张五元和5张一元”；
“一共就这四种，没错吧”。
“啧啧，厉害呀罗拉，直接列举出来了，你数学一定是数学老师教的。”八哥一副死猪不怕开水烫的样子。
“咦...,别阴阳怪气的，赶紧后面的问题，说好了，和前面一系列的，别换题目”罗拉嫌弃地摆摆手。
“放心，绝对是一系列的，而且是亲生儿砸，请听题”，八哥正声道。
“请问，用上述的纸币分别凑成50元，100元，1000元分别有几种方法？”。
“你丫存心的吧，这我要算到什么时候，你要是再来个10000，我直接认输得了？”。罗拉这火爆脾气可忍不了。
“谁让你手算了，你可以把这个当成面试题，实现一个算法试试？”八哥哑然失笑。
“算法？算法也许能实现，但是超出我现在能力范围好吧，这个不符合要求。”罗拉忿忿道。
“不对啊，这怎么超出你能力范围呢，前两天不是刚跟你说了那啥吗？你难道忘了？”八哥瞪大眼睛一副不敢置信的样子。
“前两天？动态规划？”罗拉恍然大悟。
“对啊，这货长得不够动态？以致你认不出来？算了不扯了，你按照动态规划的思路先分析分析吧。”八哥无奈道。
接下来，罗拉一顿分析猛如虎：
“嗯，我试试”。
“首先，我有{1,5,10}三种币值，如果凑出n的组合数量有f(n)” ；
“那么接下来我就得拆分f(n)，将他分成更小的子问题”；
“由于我的币值只有三种，所以只能拆出f(n-1),f(n-5),f(n-10)”;
“又因为，这三种都是可以得到f(n),所以他们之间的关系为f(n) = f(n-1) + f(n-5) + f(n-10)”
“最后得考虑边界值，边界的起始是n=1，此时可选的方案f(1)=1”。
“不对哦，你想想起始真的是n=1嘛？” 罗拉分析得正深入的的时候，八哥打断了她的思路。
“不是吗？1 是我们可以直接确定的吧？”罗拉不解。