拼凑硬币

Num = int(input())
dp = {0: 0, 1: 1, 2: 2}
def dfs(n):
    if n < 3:
        return dp[n]
    else:
        if n in dp:
            return dp[n]
        if n % 2 == 0:               # n为偶数时，要么选取0个1，要么选取2个1.
            dp[n] = dfs(n >> 1) + dfs((n-2) >> 1)
            return dp[n]
        else:                        # n为奇数时，单个1为必选项，转而考虑偶数n-1，
            dp[n] = dfs((n-1) >> 1)  # 此时偶数n-1完全由多个2的k（k>0）次幂相加而成
            return dp[n]             # 等式两边同除2，解集个数不变，可得转态转移方程
print(dfs(Num))

import sys
import math
n = int(sys.stdin.readline())
mem = {-1:0,0:1,1:1}

def get_num(n):
    if n in mem:
        return mem[n]
    else:
        m = int(math.log2(n))
        ans = get_num(n-2**m) + get_num(2**(m+1)-2-n)
        mem[n] = ans
        return ans
print(get_num(n))