算法系列-动态规划(3):找零钱、走方格问题

最近在捣鼓算法,所以写一些关于算法的文章
此系列为动态规划相关文章。

系列历史文章:
算法系列-动态规划(1):初识动态规划

算法系列-动态规划(2):切割钢材问题

算法系列-动态规划(3):找零钱、走方格问题

找零钱问题,凑数问题

最近老币越来越值钱,是投资的一个好方向。

这不,八哥从某鱼入手了几张老币。

这是一块的:

算法系列-动态规划(3):找零钱、走方格问题

这是五块的:

算法系列-动态规划(3):找零钱、走方格问题

这是十块的:

算法系列-动态规划(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 是我们可以直接确定的吧?”罗拉不解。

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张

“嗯,可以,我还以为你会按照之前的循环来写呢,想不到没入坑。” 八哥悻悻道。

“哼,我又不傻,公式我都写出来,还怕写不出代码?哈哈,赶紧的,愿赌服输,把你宝贝给我捂几天。”罗拉一副小人得志的样子。

“诺,拿去,你可要好好保护它们啊。”在把钱交出的瞬间,八哥心如刀割。没办法,即使不打赌也得交出去。哎....

走方格

三天后,晚上六点,罗拉下班回到家了,略带笑容,显然心情不错。

“咦,罗拉今天怎么这么早?有啥开心事,看你乐得。”八哥疑惑

“今天事情工作比较简单,所以没那么忙,今天公司下午茶玩游戏,赢了点零食。”罗拉想到开心的事情,不觉语气欢快起来了。

“游戏?啥游戏?”

“走方格,从一个格子走到另一个格子有多少种走法。我答得比较快。碾压同事”罗拉一副快夸我的样子。

“走方格?是不是从左上角到右下角,只能向下或向右的走法,像这样的?”八哥好像想起了什么,拿起纸笔随手画了一个图。

算法系列-动态规划(3):找零钱、走方格问题

“是的,你知道?要不我们玩玩?”罗拉看了一眼,显然对自己很自信。

“好啊,不过得来点彩头吧。”

“哟,说的好像你已经赢了似的,你想要啥彩头?”

“那啥,旧币你把玩了三天了,是不是该让我捂一下了?”

“原来你打的是这主意...”罗拉没好气地说道。

“不过也无所谓,我觉得我不会输,这样,我们各写一组数组(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 - 1m - 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优化的原理

“算我输了,你宝贝等下就还你,话说这个岂不是用数学方法更快?”罗拉赌品还是可以的。

“所以我说了对于这个问题是个样啊,我只要稍微变化一下,公式就不好使了”

“是吗?举个栗子看看” 罗拉来了兴趣。

“行,看在你赌品不错的份上,举了例子”

走格子最短路径

“从前有个公主,被魔王抓了,关在魔窟”

“一个勇敢王子准备前往魔窟营救公主,这个过程充满危险,稍有不慎就会有生命危险。”

“魔王在王子的必经之路上布满了陷阱,每一个陷阱都会对王子造成伤害,地图如下所示”

算法系列-动态规划(3):找零钱、走方格问题

“王子开始在左上角,每次只能往左或往右走一步,由于魔王布了陷阱,每走一步都会失去部分生命值”

“王子有初始生命,请问王子能否成功救出公主”?

“这案例就没法用排列组合来做了,应为不是每个格子都是一样的数字了。”八哥不紧不慢的举了个例子。

“好像是诶,排列组合有点难,感觉动态规划挺好做的吧”罗拉想了一会,还是放弃用排列组合了。

“是的,你可以试试动态规划怎么做呗。”

“嗯,我看看,也做了好多题了,看看能不能独立做出来,你别给我提示了,我先理一下” 看来罗拉干劲十足啊。

“王子有初始血量,想要成功就出公主就不能半路给跪了”
“要救出公主,只要我失去的生命值小于初始生命值,就可以了”
“只要求出所有路径所损失生命值的最小值和王子初始生命值做对比,就可以知道王子有没有可能救出公主了”
“所以这个也是一个求最小值的问题”

罗拉显然思路很清晰

“接下来就是分析一下动态规划要怎么做了”
“用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];
        //起始位置为0
        dp[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

“嗯,不错,看来动态规划你掌握的不错了。”八哥看了看结果,点头笑道。

“做多了几道题,感觉就这么回事,没啥难度。”罗拉不免翘起了尾巴。

“别开心的太早,明天我找个经典案例给你试试?”八哥不怀好意道

“没问题,今晚出去吃吧,难得这么早下班。”

“好啊,等下,我先把宝贝放好先”。

欢迎关注【兔八哥杂谈】,会持续分享更多内容.

发表评论

相关文章