美文网首页
12_2找零钱

12_2找零钱

作者: X_Y | 来源:发表于2017-09-28 21:31 被阅读9次

有数组penny,penny中所有的值都为正数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim(小于等于1000)代表要找的钱数,求换钱有多少种方法。

给定数组penny及它的大小(小于等于50),同时给定一个整数aim,请返回有多少种方法可以凑成aim。

测试样例:
输入:[1,2,4],3,3
返回:2

class Exchange {
public:
    int countWays(vector<int> penny, int n, int aim) {
        // write code here
        vector< vector<int> > dp(n, vector<int> (aim+1, 0));
        for(int i=0; i<n; i++){ dp[i][0] = 1; }
        for(int j=1; j*penny[0] <= aim; ++j) { dp[0][j*penny[0]] = 1;}
        for(int i=1; i<n; ++i){
            for(int j=1; j<=aim; ++j){
                dp[i][j] = dp[i-1][j] + (j-penny[i] >= 0 ? dp[i][j-penny[i]] : 0);
            }
        }
        return dp[n-1][aim];
    }
};

相关文章

  • 12_2找零钱

    有数组penny,penny中所有的值都为正数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再...

  • 背包问题详解

    目录 问题引入 在介绍背包问题之前,我们先来看一个小问题:找零钱问题。 找零钱问题 背包问题的一个浅显版本是找零钱...

  • 【找零钱】

    用python写一个找零钱的算法。 零钱共有50块,20块,10块,5块,和1块,共5种。。例:69 = 50 +...

  • 找零钱

    10人以上 如:男生1元,女生0.5元 围城一圈,中间站一人 主持人:“大家都来找零钱” 大家问:“找多少?” 主...

  • 找零钱

    给定一个数组,数组中为不同的数代表不同钱的面值,同时给定一个需要兑换零钱的钱数,任意使用不同面值不同数量的钱来兑换...

  • 算法思想之动态规划(三)——找零钱问题

    前言 今天我们继续讨论经典的动态规划问题之找零钱问题。 找零钱问题 问题描述 假设你是一名超市收银员,现有种不同面...

  • 找零钱问题

    问题 这个题目要求编写一段程序实现统一银座超市的找零方案。只需输入要补给顾客的 金额,然后通过程序就可以计算出该金...

  • 零钱找零

    零钱找零问题,题目是这样的 例如: 解决这样的问题,可以使用到的方法有贪心算法、暴力递归或lookback、动态规...

  • 贪心--找零钱

    目录[https://www.jianshu.com/p/85e18c21317a] 题号[https://lee...

  • 找零的技巧(日更第107天)

    曾经帮亲戚家卖鞭炮的时候,说起了找零的话题,说要是找钱,先找零钱,在找整的,也许顾客没有等到你给他整钱,他就...

网友评论

      本文标题:12_2找零钱

      本文链接:https://www.haomeiwen.com/subject/nwnvextx.html