拼凑硬币

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

#include<iostream>
using namespace std;
int check(long long m)
{
    int num = 0, coin = 1;
    int c, cb;
    for (int i = 0;m != 0; i++)
    {
        c = m % 2;
        m /= 2;
        if (i == 0)
            cb = c;
        else
        {
            if (cb == 1 && c == 0)
                cb = 0;
            else if (cb == 0 && c == 0)
            {
                cb = 0;
                coin *= ++num;
                num = 0;
            }
            else if (cb == 0 && c == 1)
                num++;
        }
    }
    if (num)
        coin *= ++num;
    return coin;
}

int main()
{
    long long m;
    while (cin >> m)
    {
        cout << check(m) << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

map<long, long> mp;

long F(long n){
    if(mp.find(n) != mp.end())
        return mp[n];
    long cnt = 0;
    if(n&1 == 1)
        cnt = F(n/2);
    else
        cnt = F(n/2) + F(n/2-1);
    mp[n] = cnt;
    return cnt;
}

int main(){
    mp[0] = mp[1] = 1;
    long n;
    scanf("%ld", &n);
    cout<<F(n)<<endl;
    return 0;
}

二楼思路实现一下

记忆搜索实现递归(直接递归会有大量重复计算容易栈溢出) 用map来保存

#include<iostream>
#include<map>
using namespace std;
map<long, long> m;

long solve(long n){  //记忆搜索法 
    if(m.count(n)) return m[n]; //如果已有直接返回
    long count = 0;
    if((n&1) != 1) count = solve(n>>1) + solve((n>>1)-1);  //n为偶数
    else count = solve(n>>1);  //n为奇数
    m[n] = count;
    return count;
}

int main(){
    m[0] = 1; m[1] = 1;  //初始值
    long n; cin>>n;
    cout<<solve(n)<<endl;
    return 0;
}

动态规划
import java.util.*;

public class Main{
    public static void  main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            long n = sc.nextLong();
            System.out.println(helper(n));
        }
    }
    static long helper(long n){
        List<Integer> list = new ArrayList<>();
        while(n > 0){
            list.add((int)(n % 2));
            n /= 2;
        }
        long[][] dp = new long[list.size()][2];
        dp[0][list.get(0)]++;
        for(int i = 1 ; i < list.size() ; i++){
            if(list.get(i) == 0){
                dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
            }else{
                dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
                for(int j = i - 1 ; j >= 0 ; j--){
                    dp[i][0] += dp[j][0];
                    if(list.get(j) == 1){
                        break;
                    }
                }
            }
        }
        return dp[dp.length - 1][0] + dp[dp.length - 1][1];
    }
}

参考一二楼思路，简化了下代码，因为不需要有序，认为使用unordered_map更优。

#include <iostream>
#include <unordered_map>
using namespace std;

#define ll long long
unordered_map<ll, ll> m = {
    {1, 1},
    {2, 2}
};

int func(ll n) {
    if (m[n]) return m[n];
    int ans;
    if (n % 2) {
        ans = func(n >> 1);
    } else {
        ans = func((n - 2) >> 1) + func(n >> 1);
    }
    return m[n] = ans;
}

int main() {
    ll n;
    cin >> n;
    cout << func(n) << endl;
    return 0;
}

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

# 参考 desperado_xxx 提供的思路

n = input('')
n = int(n)

dp = {1: 1, 2: 2}

def fun(val):
    if dp.get(val):
        return dp[val]
    # n为奇数，则取一个1，剩下与(n-1)/2的取法一一对应
    if val % 2 == 1:
        if dp.get(val >> 1):
            dp[val] = dp.get(val >> 1)
        else:
            dp[val] = fun(val >> 1)
    # n为偶数，有两种情况
    # 1. 取两个1，剩下与(n-2)/2的取法一一对应
    # 2. 不取1，剩下与n/2的取法一一对应
    else:
        if not dp.get(val >> 1):
            dp[val >> 1] = fun(val >> 1)
        if not dp.get(val >> 1 - 1):
            dp[val >> 1 - 1] = fun((val >> 1) - 1)
        dp[val] = dp[val >> 1] + dp[(val >> 1) - 1]

    return dp[val]


print(fun(n))

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
public class Main {
    private static Map<Long,Long> map=new HashMap<>();
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        map.put(0L,1L);
        map.put(1L,1L);
        long n=in.nextLong();
        System.out.println(cal(n));
    }
    private static Long cal(long n) {
        if(map.containsKey(n)) {
            return map.get(n);
        }
        long result1=cal(n>>1);
        map.put(n>>1,result1);
        Long result;
        if(n%2==1) {
            result=result1;
        }else {
            long result2=cal((n>>1) -1);
            map.put((n>>1)-1,result2);
            result=result1+result2;
        }
        map.put(n,result);
        return result;
    }
} 

// 时间复杂度过高，不能通过；没什么技巧，就是将和拆分成最长子串相加，然后通过这个子串去
// 反向求解
// 例如 6：
// 1、先找到最靠近的2幂次方，这里很容易知道是4，然后建立一个数组，以2的n次方的n对应数组下标
// 即1就对应a[0],2对应a[1],4对应a[2]…… 数组的长度为n+1(如果sum为2的幂次方，那么n+2)，其中2^n = 4
// 2、然后找到4的最长子串，容易知道这里就是递归了，下面会说如何递归。最后结果是 1+1+2
// 3、另一个加数为 6-4 = 2.这里也算出2的最长子串，结果是 1+1
// 4、所以最后的子串是 1+1+1+1+2，这里不满足题意，所以要进行调整，
// 5、调整的话，就是将数组中元素超过2的元素相加，那么元素个数就-2，后一个元素个数就+1
// [4,1,0]，此时4大于2，对应的数字为 1，那么由 1+1 = 2，a[0] 变为2,a[1]变为 2；此时a[1]大于2，结果就是[2,2,0]
   即变为 1+1+2+2，这个就满足题意
//6、对这个 1+1+2+2 进行解决，因为我们知道 1+1+2+2 -> 2+2+2(不满足) -> 2+4   1+1+2+2 -> 1+1+4 这种不断递归就可以就可以得出
// 有几种方案，那如何进行递归呢，首先我们知道到这一步时，数组中的元素已经是满足条件的了，即一开始的数组不会出现超过2的元素个数
// 所以我们可以对个数等于2的元素本身进行累加，那么相加后本身元素个数就-2，而后一个元素的个数加+1,这里跟调整是同理的；
// 在调整过程中可能出现个数超过2的个数，那么包含这个超过2的元素都是不符合条件的，那么就不用继续遍历下去，直接返回

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        if(sc.hasNextLine()){
            long sum = sc.nextLong();
            if(sum == 1){
                System.out.println(1);
            }
                 // 得出第一个最靠近和的2的幂数
            long f1 = calNumber(sum);
                  // 通过这个数可以知道最大的数就是本身，
            int length = calIndex(f1);
                  // 如果和本身就是 2 的幂次方，那么最大的数是和本身，那么长度还要加1
            if((sum & sum-1) == 0){
                length++;
            }
                  // 上面假设最大的数是4，那么可知2^2 = 4，那么数组长度就为3(2+1)，此时a[2] 下标才不会越界
            long[] array = new long[length+1];
                  // 例如 8，那么是2的幂次方，所以要建立的数组是4位，因为才有a[3]
                  // 而对于20，最大的数是16，即2^4,所以要建立的数组是5位，才有a[4]

                  // 进行最长子串求解，结果放在传入的 array 中
            lastestHelp(sum,array);
                  // 调整array，因为会出现不符合条件的个数
            adjust(array);
                  // 通过调整后的array求解，
            int result = calHelp(array,0);
            System.out.println(result);
        }
    }
    protected static void lastestHelp(long i,long[] array){
        if(i == 1){
            array[0] ++;
            return;
        }
        long ftemp1 = calNumber(i);
        long ftemp2 = i - ftemp1;
        if(ftemp1 == ftemp2){
            array[calIndex(ftemp2)] ++;
            lastestHelp(ftemp1,array);
            return;
        }
        lastestHelp(ftemp1,array);
        lastestHelp(ftemp2,array);
    }

    protected static long calNumber(long sum){
        int i1 = 0;
        long i2 = 1;
        while(i2 < sum){
            i2 = 1L << i1;
            i1++;
        }
        i2 >>>= 1;
        return i2;
    }

    protected static int calIndex(long num){
        int result = 0;
        while((num & 1) != 1){
            num >>>= 1;
            result++;
        }
        return result;
    }

    protected static void adjust(long[] array){
        // 调整元素
        for(int i = 0;i<array.length;i++){
            while(array[i] > 2){
                array[i+1]++;
                array[i] -= 2;
            }
        }
    }

    protected static int calHelp(long[] array,int start){
        int result = 0;
        //通过数组算出结果
        for(int i = start;i<array.length;i++){
            if(array[i] >= 2){
                        // 通过深拷贝，保存原数组内容
                long[] tempArray = new long[array.length];
                System.arraycopy(array,0,tempArray,0,array.length);
                array[i+1] ++;
                array[i] -= 2;
                        // 每次查询从下一位开始，因为本身已经被上一个进行累加了，并且本身大于等于2
                result += calHelp(array,i+1);
                        // 上一步遍历如果本身元素大于2的话，在上一个遍历中会被累加分散，所以是满足题意的，但是到这一步时
                        // 已经变为原数组了，如果此时元素有大于3的话，就不用继续循环遍历了，直接返回。
                        // 例如[2,2,0,0]，变为[0,3,0,0],然后3 > 2，进入遍历变成[0,1,1,0]，因为没有大于2的元素了，所以for遍历也不会进入循环
                        // 返回 1，此时回到下面这个方法，此时 tempArray = [0,3,0,0]，发现本身3大于2，所以可以得知不用进行下一个循环，因为3不符合条件，就算后面符合都没用，所以直接返回结果（不用加1，直接返回，因为本身不满足条件）
                array = tempArray;
                if(array[i] > 2){
                    return result;
                }
            }
        }
        return result+1;
    }
}