首页 > 试题广场 >

硬币划分

[编程题]硬币划分
  • 热度指数：2058 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？

输入描述:
输入整数n.(1<=n<=100000)


输出描述:
输出组合数，答案对1e9+7取模。
示例1

输入

13

输出

16
算法知识视频讲解
添加回答
Python
elij头像 elij 
def calc(n):
    n = int(n)
    coins = [1, 2, 5, 10]
    
    memo = [0] * (n + 1)
    memo[0] = 1
    
    for i in coins:
        for j in range(i, n+1):
            # 必须与此数取模而非题目给的 1e9+7
            memo[j] = (memo[j] + memo[j-i]) % 1000000007

    return memo[n] 
    
print(calc(input()))

编辑于 2019-10-26 00:38:02 回复(0)
Python
xiaoghggghgg头像 xiaoghggghgg 


n = int(input())
n_5 = n//5
idea = 0
for x in range(n_5+1):
    idea += (x//2+1)*((n-5*x)//2+1)
print(int(idea%(1e9+7)))


 运行时间： 46 ms 占用内存：3556K
编辑于 2019-09-28 22:30:59 回复(0)
Python
0b100001101000头像 0b100001101000 
n = int(input())
m = [1] + [0]*n
for i in (1,2,5,10):
    for j in range(i,n+1):
        m[j] = (m[j] + m[j-i]) % 1000000007
print(m[-1])


发表于 2019-09-17 01:11:20 回复(0)
Python
龙江头像 龙江
#请帮忙看看哪里有问题，部分通过，大数不行
#枚举，从大到小，依次枚举计数
n = int(input(''))
list1=0
for i in range(0,(n//10)+1):
    shi = 10*i
    for j in range(0,((n-shi)//5)+1):
        wu = 5*j
        list1=list1+((n-shi-wu)//2)+1
print(list1)
编辑于 2019-09-12 22:25:21 回复(1)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 c#工程师 数据库工程师 瓜子二手车 2019 大数据开发工程师 Java工程师
上传者：小小
难度：
4条回答 9462浏览

热门推荐

通过挑战的用户

相关试题

硬币划分

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号