题目
题目来源：
Link
分析
每一步的选择都依赖前一步的选择，是前面选择的组合，子问题重合，所以用动态规划
代码
package com.graph;
import java.util.*;
public class Solution {
public int solve(int n){
if(n==0) return 1;
String binary = Integer.toBinaryString(n);
int len=binary.length();
int[] f = new int[len+1];
f[0]=1;
f[1]=2;
//计算场i的二进制位符合要求的个数
for(int i=2; i<=len; i++) {
f[i] = f[i-1]+f[i-2];
}
//计算0~n的符合要求的总个数
int sum=0;
for(int i=0, k=len; i<len; i++,k--) {
if(binary.charAt(i)=='1') {
sum+=f[k-1];
if(i>0 && binary.charAt(i-1)=='1') {
return sum;
}
}
}
//先前没有return，到这里，说明n本身没有算进去
sum++;
return sum;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.solve(9));
}
}
