首页 > 试题广场 >

拼凑硬币

[编程题]拼凑硬币
  • 热度指数：6697 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解

小Q十分富有，拥有非常多的硬币，小Q拥有的硬币是有规律的，对于所有的非负整数K，小Q恰好各有两个面值为2^K的硬币，所以小Q拥有的硬币就是1,1,2,2,4,4,8,8,…。小Q有一天去商店购买东西需要支付n元钱，小Q想知道有多少种方案从他拥有的硬币中选取一些拼凑起来恰好是n元（如果两种方案某个面值的硬币选取的个数不一样就考虑为不一样的方案）。

 


输入描述:
输入包括一个整数n(1≤n≤10^18)，表示小Q需要支付多少钱。注意n的范围。


输出描述:
输出一个整数，表示小Q可以拼凑出n元钱放的方案数。
示例1

输入

6

输出

3
算法知识视频讲解
开通博客
头像 久81
发表于 2022-05-30 23:04:12
借鉴了讨论区各位的思路 设 f(n)f(n)f(n)：凑出n元的方案数 情况1：n是奇数 ​  n为奇数，则必然需要一个1元钱（不论用哪个一元钱都是一样的；另一个1元必然不用），则f(n)=f(n−1)f(n)=f(n-1)f(n)=f(n−1) ​  对偶数f(n−1)f(n-1)f(n−1)：用 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 17c89
发表于 2024-03-20 15:54:57
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { private static Map<Long, Long> mem; publ 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
上传者：小小
难度：
18条回答 6516浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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