深度探索算法系列之动态规划：找零钱、走方格问题这次彻底搞懂格子算法怎么算

深度探索算法系列之动态规划：找零钱、走方格问题这次彻底搞懂最近在捣鼓算法，所以写一些关于算法的文章此系列为动态规划相关文章。
找零钱问题，凑数问题最近老币越来越值钱，是投资的一个好方向。
这不，八哥从某鱼入手了几张老币。
这是一块的：

文章插图
这是五块的：

文章插图
这是十块的：

文章插图
不得不说，老币还是挺好看的
看看这成色，过几年一定很值钱，这就是我留给我孩子的财产。
但是不小心给罗拉看到了，然后就有了下面的对话....

文章插图
找零钱的方式钱？她能力范围？又不太简单？动态规划？八哥脑子一动，马上就想到一个题目。
于是，虎躯一震，眉头一舒，摸摸下巴，点点头。
“有了，罗拉请听题”
“你看，我这里的旧币有面值{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是我们可以直接确定的吧？”罗拉不解。
“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张

“嗯，可以，我还以为你会按照之前的循环来写呢，想不到没入坑。” 八哥悻悻道。
“哼，我又不傻，公式我都写出来，还怕写不出代码？哈哈，赶紧的，愿赌服输，把你宝贝给我捂几天。”罗拉一副小人得志的样子。
“诺，拿去，你可要好好保护它们啊。”在把钱交出的瞬间，八哥心如刀割。没办法，即使不打赌也得交出去。哎....
走方格三天后，晚上六点，罗拉下班回到家了，略带笑容，显然心情不错。
“咦，罗拉今天怎么这么早？有啥开心事，看你乐得。”八哥疑惑
“今天事情工作比较简单，所以没那么忙，今天公司下午茶玩游戏，赢了点零食。”罗拉想到开心的事情，不觉语气欢快起来了。
“游戏？啥游戏？”
“走方格，从一个格子走到另一个格子有多少种走法。我答得比较快。碾压同事”罗拉一副快夸我的样子。
“走方格？是不是从左上角到右下角，只能向下或向右的走法，像这样的？”八哥好像想起了什么，拿起纸笔随手画了一个图。

文章插图
“是的，你知道？要不我们玩玩？”罗拉看了一眼，罗拉显然对自己很自信。
“好啊，不过得来点彩头吧。”
“哟，说的好像你已经赢了似的，你想要啥彩头？”
“那啥，旧币你把玩了三天了，是不是该让我捂一下了？”
“原来你打的是这主意...”罗拉没好气地说道。
“不过也无所谓，我觉得我不会输，这样，我们各写一组数组(l1,l2)和(b1,b2)，分别组成l1 * b1,l2 * b2的格子，然后计算，看谁先算出两个，一局定胜负，可以吧？” 。
“嗯，很公平，我没问题，开始吧。” 八哥胸有成竹。
走方格（走法数量）不一会儿，两人都把纸条写好了。
摊开纸条
罗拉写的是(3,6)
八哥写的是(7,5)
“我们现在要计算3 * 7 ,6 * 5的方格走法，即使开始” 。罗拉说完，拿起纸笔，画了起来，赢在了起跑线。
30秒后
“嘿嘿，分别为 28 和 126”，不到一分钟，八哥便说出了答案。
“你瞎说的吧，我第一个都还没算完呢，你两个都完了？”
“山人自有妙计，你输了”
“等我算完再说，谁知道你的对的还是错的？”
“可是你要是自己算错了或算很久那不是浪费时间？”
“不然捏，我总得验证结果吧？”罗拉忍不住翻白眼。
“看你画了这么多图，挺辛苦的，动动脑子，我要是在你公司，今天这游戏就通杀了？”
“咦，难道有规律？”罗拉自动忽略八哥的后半句话。
“你三天前怎么赢得我的旧币的？你想想？”
“赢钱？打赌啊，不对，难道是动态规划？”
“是啊，你怎么每次都得提醒才想得起来啊”八哥无奈道。
“谁知道你连这都埋个坑？行了，我知道接下来该分析分析了。”
“假设到最右下角的方式有f(n),由于只能往左边或下面走，所以f(n)=f(上边)+f(左边)”
“嗯...其实用二维数组表示好像更好，应该表示为dp[x][y]=dp[x-1][y]+dp[x][y-1]”
“接下来就是子问题的计算，直到边界”
“这里的边界，应该是有沿着墙边走，因为只能向左或向右，所以dp[x][0]=0,dp[0][y]=0”
“接下来代码实现”

public class WalkGrid {public static void main(String[] args) {System.out.println("3*7方格走法共有："+walk(3,7)+" 种");System.out.println("5*6方格走法共有："+walk(5, 6)+" 种");}public static int walk(int n, int m) {int[][] dp = new int[n][m];//定义边界for (int i = 0; i < n; i++) dp[i][0] = 1;for (int i = 0; i < m; i++) dp[0][i] = 1;//双重循环，计算dp数组的值for (int i = 1; i < n; i++)for (int j = 1; j < m; j++)dp[i][j] = dp[i - 1][j] + dp[i][j - 1];return dp[n - 1][m - 1];}}//输出结果3*7方格走法共有：28 种5*6方格走法共有：126 种

“咦你的答案没错诶。不对，你没写代码，而且一分钟都不到，这肯定不是最快的。”罗拉突然醒悟。
“对于这个题目，当然不是最快的，你想一下，对于n * m的格子，我一共要走多少步？向上多少，向下多少？”
“向下是n-1，向右是m-1,一共是m + n - 2,可是这个和你算得快没啥关系吧？”罗拉不解
“谁说没关系，一共m + n - 2,我只要确定向下或向右走的，另一个方向的是不是也确定了？换言之，就是m + n - 2中选n - 1 或 m - 1吧，你发现了什么？”
“从总数里面选出某些...吖，是排列组合的组合，这是一个数学问题”罗拉恍然大悟。
“是的，这里可以看成是组合问题，通过组合共识，10以内的分分钟就算出来了不过分吧，你甚至可以试着代码实现”八哥得意说道
“行吧，我试试，你就是想我写代码吧，我想一下组合公式组合数计算方法，从N项中选出M项:f(n,m) = n! / ((n - m)! * m!)”
“代码就是这样”

public class WalkGrid {public static void main(String[] args) {System.out.println("3*7方格走法共有：" + cal(3, 7) + " 种");System.out.println("5*6方格走法共有：" + cal(5, 6) + " 种");}public static int cal(int n, int m) {int tot = m + n - 2;int res = 1;int max = Math.max(m - 1, n - 1);//公式中tot！与max！部分可以抵消max！部分，减少计算量for (int i = tot; i > max; i--) res *= i;for (int i = 1; i <= tot - max; i++) res /= i;return res;}}//输出结果3*7方格走法共有：28 种5*6方格走法共有：126 种

公式中的f(n,m) = n! / ((n - m)! * m!)
可以化简为f(n,m) = n*(n-1)*(n-2)...*(m+1) / (n - m)!就是代码中max优化的原理

“算我输了，你宝贝等下就还你，话说这个岂不是用数学方法更快？”罗拉毒品还是可以的。
“所以我说了对于这个问题是个样啊，我只要稍微变化一下，公式就不好使了”
“是吗？举个例子看看” 罗拉来了兴趣。
“行，看在你赌品不错的份上，举了例子”
走格子最短路径“从前有个公主，被魔王抓了，关在魔窟”
“一个勇敢王子准备前往魔窟营救公主，这个过程充满危险，稍有不慎就会有生命危险。”
“魔王在王子的必经之路上布满了陷阱，每一个陷阱都会对王子造成伤害，地图如下所示”

文章插图
“王子开始在左上角，每次只能往左或往右走一步，由于魔王布了陷阱，每走一步都会失去部分生命值”
“王子有初始生命，请问王子能否成功救出公主”？
“这案例就没法用排列组合来做了，因为不是每个格子都是一样的数字了。”八哥不紧不慢的举了个例子。
“好像是诶，排列组合有点难，感觉动态规划挺好做的吧”罗拉想了一会，还是放弃用排列组合了。
“是的，你可以试试动态规划怎么做呗。”
“嗯，我看看，也做了好多题了，看看能不能独立做出来，你别给我提示了，我先理一下” 看来罗拉干劲十足啊。
“王子有初始血量，想要成功就出公主就不能半路给跪了”
“要救出公主，只要我失去的生命值小于初始生命值，就可以了”
“只要求出所有路径算损失生命值的最小值和王子初始生命值做对比，就可以知道王子有没有可能救出公主了”
“所以这个也是一个求最小值得问题”
罗拉显然思路很清晰
“接下来就是分析一下动态规划要怎么做了”
“用dp[x][y]记录走到(x,y)时损失的生命值”
“由于只能向左或向右，所以相关的子问题为dp[x][y]=dp[x-1][y]+dp[x][y-1]”
“接下来考虑边界问题”
“向右只有一条路经，所以dp[x][0]=dp[x-1][0]+(x,0)”
“向下也只有一条路dp[0][y]=dp[0][y-1]+(0,y)”
“入口，也就是(0,0)应该不损失生命值，所以，dp[0][0]=0”
“然后就是编写代码了”
“完事，你看看”罗拉用力敲下最后一下键盘。

public class SavePrincess {//魔王宫殿static int palaces[][] = {{0, 6, 9, 10, 12, 15},{17, 33, 32, 8, 21, 20},{3, 44, 11, 20, 1, 0}};public static void main(String[] args) {int init = 50;//初始生命值int min = save();System.out.println("王子初始血量为:" + init + "，" + (min - init >= 0 ? "不能" : "能") + "救出公主");init = 80;//初始生命值System.out.println("王子初始血量为:" + init + "，" + (min - init >= 0 ? "不能" : "能") + "救出公主");System.out.println("就出公主的损失生命值得最小值为:" + min);}/*** 拯救公主的最低损失生命值* @return*/public static int save() {int n = palaces.length;int m = palaces[0].length;int[][] dp = new int[n][m];//起始位置为0dp[0][0] = 0;//向下初始化for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + palaces[i][0];//向右初始化for (int i = 1; i < m; i++) dp[0][i] = dp[0][i - 1] + palaces[0][i];for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + palaces[i][j];}}return dp[n - 1][m - 1];}}//输出结果王子初始血量为:50，不能救出公主王子初始血量为:80，能救出公主就出公主的损失生命值得最小值为:54

“嗯，不错，看来动态规划你掌握的不错了。”八哥看了看结果，点头笑道。
“做多了几道题，感觉就这么回事，没啥难度。”罗拉不免翘起了尾巴。
“别开心的太早，明天我找个经典案例给你试试？”八哥不怀好意道
“没问题，今晚出去吃吧，难得这么早下班。”
“好啊，等下，我先把宝贝放好先” 。
推荐阅读：【深度探索算法系列之动态规划：找零钱、走方格问题这次彻底搞懂格子算法怎么算】《复杂》的作者梅拉妮?米歇尔曾经做过一项遗传算法实验（GA）。实验人员设计了一个在一块场地上画出10×10的方格，随机在格子中放一些垃圾桶。被试是机器人罗比，它的任务是捡垃圾桶。如果它能顺利地走到垃圾桶前捡起来得10分；如果走错格子、撞墙都要扣分，撞墙扣得最多，扣10分。一共可以走200下，满分是500分。最初，实验人员没有给罗比输入程序而让它随意走。第一遍它的成绩最差是-800多分，意味着200下几乎都了撞墙，而最好成绩是-81分。随后，为罗比输入了一个程序，得分是346分。接下来，实验人员让罗比继续练习，然后在这些练习中选择最好和第二好的路径（程序），从两次路径中各取一半程序拼在一起，中间随机找到几个环节变异一下，再输入给罗比。当罗比走完200次后，再选择最好和第二好程序的一半拼在一起，随机变异几个小环节，再输入给它。如此反复，迭代了1000次后，罗比的成绩高达483分，远超人类设计程序的成绩。就是说，机器人在一两个小时内就进化到了超出人类想象的程度。遗传算法对于人类社会也非常有用。例如生物进化、基因遗传等。在家庭教育中，我们也可以使用遗传算法的思维，即寻找家庭教育亮点，然后优化亮点，并将其传承下去。因此，遗传算法是家风梳理与传承的又一个有力支持。

深度探索算法系列之动态规划：找零钱、走方格问题 这次彻底搞懂 格子算法怎么算

深度探索算法系列之动态规划：找零钱、走方格问题这次彻底搞懂格子算法怎么算