传送门题意略分析由低位向高位考虑，令f(n)为n的扩展二进制数表示数1.当前数为偶数，末位为0或2，那么f(n)=f(n/2)+f(n/2-1)2.当前数为奇数，末位为1，那么f(n)=f(n/2)3.n==0,返回1其他思路1 高位向低位考虑思路2 dp转移