首页 > 试题广场 >

硬币划分

[编程题]硬币划分
  • 热度指数: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
头像 wzq0428
发表于 2019-09-26 00:12:18
emmm,一不小心捣鼓出来一个O(n)的算法…… 用数组count[i]来存储能组合出i的方案数。 一共四种硬币,从1元开始,依次考虑,比如说,只用1元来组合,显然每个i都只有一种组合方案。 现在考虑加入2元,我们事先约定小的硬币在前,大的硬币在后,那么count[i]至少由一个2元硬币组成的情况下 展开全文