“1 是可以直接确定没错，更准确地说是我们能够一眼看出。如果我要求5，我们很容易得到五个1和一个5两个方案吧，你把5代入你那个公式试试？”。
“n=5?,f(5) = f(5-1) + f(5-5) = f(4) + f(0)”
“咦，还有个f(0),也就是说f(1)=f(1-1)=f(0),这里漏了，0应该也是一种选择,所以初始状态应该是凑0,并且只有1种选择。”罗拉恍然大悟。
“是的，所以现在可以写出代码了吧？”
“嗯，稍后，这次不讲码徳直接可以写个完全版的了”罗拉自信道。
于是一顿键盘噼里啪啦，代码出炉。
public class Coin { public static void main(String[] args) { System.out.println("凑成10块的方案有："+change(10) + "种"); System.out.println("凑成10000块的方案有："+change(10000) + "种"); } public static int change(int target) { int[] coins = {1, 5, 10}; int[] dp = new int[target + 1]; dp[0] = 1; for (int coin : coins) for (int x = coin; x <= target ; x++) { dp[x] += dp[x - coin]; } return dp[target]; } } //输出结果 凑成10块的方案有：4种 凑成10000块的方案有：1002001种八哥瞄了一眼
“不错，挺熟练了，不过这个不算是自己想出来的吧，我赤裸裸的提示了吧？我换一个角度再问一下不过分吧？”
“额，可以，你问吧”罗拉老脸一红，自知理亏，只得答应八哥的要求。
找零钱的最佳方案“好，现在的问题是，我要凑出n，至少要多少张纸币？做出来，我这宝贝就给你捂几天又何妨？”。八哥撩一撩头发，笑道。
“行，我想想，大概知道怎么做了，我分析下先”，罗拉不甘示弱。
“首先对于一个f(n),我的结果可以来自f(n-1),f(n-5),f(n-10)这点和之前一样。”
“不一样的地方在于我们现在不是求和而是求最小值。”
“所以，f(n) = min(f(n-1),f(n-5),f(n-10)) + 1”
“最后再确定一下边界，初始值应该是0,f(0)=0”。
“嗯，分析的没错，show me your code。”八哥点点头。
“等等，马上。”罗拉一喜，马上开始舞动键盘。
啪啪两分钟，代码出炉。
public class Coin { static int[] coins = {1, 5, 10}; public static void main(String[] args) { System.out.println("凑成55块至少需要的纸币为：" + minCoinCnt(55) + "张"); System.out.println("凑成999块至少需要的纸币为：" + minCoinCnt(999) + "张"); System.out.println("凑成1000块至少需要的纸币为：" + minCoinCnt(1000) + "张"); } public static int minCoinCnt(int target) { int[] dp = new int[target + 1]; //凑成0元需要0张 dp[0] = 0; for (int x = 1; x <= target; x++) { dp[x] = Integer.MAX_VALUE; for (int coin : coins) { //fn(n) = min(f(n-1),f(n-5),f(n-10)),注意f(n)的n要大于等于0，所以需要(x-coin>=0) //选择纸币叫小的方案 if (x - coin >= 0) dp[x] = Math.min(dp[x], dp[x - coin] + 1); } } return dp[target]; } } //输出结果 凑成55块至少需要的纸币为：6张 凑成999块至少需要的纸币为：104张 凑成1000块至少需要的纸币为：100张“嗯，可以，我还以为你会按照之前的循环来写呢，想不到没入坑。” 八哥悻悻道。
“哼，我又不傻，公式我都写出来，还怕写不出代码？哈哈，赶紧的，愿赌服输，把你宝贝给我捂几天。”罗拉一副小人得志的样子。
“诺，拿去，你可要好好保护它们啊。”在把钱交出的瞬间，八哥心如刀割。没办法，即使不打赌也得交出去。哎....
走方格三天后，晚上六点，罗拉下班回到家了，略带笑容，显然心情不错。
“咦，罗拉今天怎么这么早？有啥开心事，看你乐得。”八哥疑惑
“今天事情工作比较简单，所以没那么忙，今天公司下午茶玩游戏，赢了点零食。”罗拉想到开心的事情，不觉语气欢快起来了。
“游戏？啥游戏？”
“走方格，从一个格子走到另一个格子有多少种走法。我答得比较快。碾压同事”罗拉一副快夸我的样子。
“走方格？是不是从左上角到右下角，只能向下或向右的走法，像这样的？”八哥好像想起了什么，拿起纸笔随手花了一个图。
“是的，你知道？要不我们玩玩？”罗拉看了一眼，罗拉显然对自己很自信。
“好啊，不过得来点彩头吧。”
“哟，说的好像你已经赢了似的，你想要啥彩头？”
“那啥，旧币你把玩了三天了，是不是该让我捂一下了？”
“原来你打的是这主意...”罗拉没好气地说道。