（dp）LeetCode Weekly Contest 34 -Non-negative Integers without Consecutive Ones

Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.

Example 1:

Input: 5
Output: 5
Explanation: 
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

Note: 1 <= n <= 1e9

为解决本题，首先需要考虑n位二进制数码，有多少种组合满足：不存在连续的1

n=1时显然为2，n=2时为3,下面考虑n>=3的情况。设该数列为an

①尾数为0 则不考虑尾数，只看前n-1位必定亦满足该条件 情况数为an-1

②尾数为1，则倒数第二位一定为0 （否则已经存在连续的1） 情况数为an-2

故得到递推公式 an=an-1+an-2 即为斐波那契数列

回到题目，考虑两个例子

若为1010100 则情况数为a[6]+a[4]+a[2]+1

若为 1011010 则情况数为a[6]+a[4]+a[3]

分析后发现求解步骤。遇到1加上a[i]（i为该1的下标，从末尾下标为0开始计算）遇到连续两个1后加上了就终止循环。如果加到最后才停止，说明本身该数也是满足要求的，答案+1

class Solution {
public:
    int f[40];
    int a[40];
    int findIntegers(int num) {
        f[0]=1;f[1]=2;
        for(int i=2;i<=36;i++)
            f[i]=f[i-1]+f[i-2];
        int cnt=0;
        while(num)
        {
            a[cnt++]=num%2;
            num/=2;
        }
        int an=0,i,la=0;
        for(i=cnt-1;i>=0;i--)
        {
            if(a[i]==1)
            {
                an+=f[i];
                if(la==1)
                    break;
            }
            la=a[i];
        }
        if(i==-1)
            ++an;
        return an;
    }
};