题解 | #拼凑硬币#

#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))