题解 | #拼凑硬币#
拼凑硬币
https://www.nowcoder.com/practice/2479839aa61e44f39aa3268160650e17
解题思路
- 小Q拥有面值为
的硬币,每种面值有两个
- 需要计算用这些硬币拼出目标金额
的不同方案数
- 关键发现:
- 对于偶数
,可以选择使用或不使用面值为2的硬币
- 对于奇数
,只能从
的方案转移而来
- 对于偶数
- 使用记忆化搜索,避免重复计算
代码
#include <iostream>
#include <map>
using namespace std;
map<long long, long long> memo;
long long solve(long long n) {
// 已计算过的值直接返回
if (memo.count(n)) return memo[n];
long long count = 0;
if (n % 2 == 0) {
// 偶数:可以选择使用或不使用面值为2的硬币
count = solve(n/2) + solve((n-2)/2);
} else {
// 奇数:只能从n/2的方案转移
count = solve(n/2);
}
memo[n] = count;
return count;
}
int main() {
// 初始化基础情况
memo[0] = memo[1] = 1;
long long n;
cin >> n;
cout << solve(n) << endl;
return 0;
}
import java.util.*;
public class Main {
static Map<Long, Long> memo = new HashMap<>();
static long solve(long n) {
// 已计算过的值直接返回
if (memo.containsKey(n)) return memo.get(n);
long count = 0;
if (n % 2 == 0) {
// 偶数:可以选择使用或不使用面值为2的硬币
count = solve(n/2) + solve((n-2)/2);
} else {
// 奇数:只能从n/2的方案转移
count = solve(n/2);
}
memo.put(n, count);
return count;
}
public static void main(String[] args) {
// 初始化基础情况
memo.put(0L, 1L);
memo.put(1L, 1L);
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
System.out.println(solve(n));
}
}
from functools import lru_cache
@lru_cache(None)
def solve(n):
if n == 0 or n == 1:
return 1
if n % 2 == 0:
# 偶数:可以选择使用或不使用面值为2的硬币
return solve(n//2) + solve((n-2)//2)
else:
# 奇数:只能从n/2的方案转移
return solve(n//2)
n = int(input())
print(solve(n))
算法及复杂度
- 算法:记忆化搜索(动态规划)
- 时间复杂度:
- 每个状态只计算一次,状态数与n的二进制位数相关
- 空间复杂度:
- 需要存储所有中间状态的结果