A digit DP

bernays , Learn a number in one night dp Not bad, hehe
As the title ：
600. There is no continuity 1 Non-negative integer
Given a positive integer n , The return range is [0, n] All nonnegative integers , Its binary representation does not contain Successive 1 The number of .
Namely dp[i][j] Express i The number of digits is j start , How many kinds are there .
In this case dp[i][j]=dp[i-1][k]( Sum according to the right ）
Then there may be a mess of rules in the title , For example, continuous 1, Discontinuous 1, Does not contain a certain number … wait ; At this time, just change dp Array can , But notice , Inside dp Just initialize .
If it is to ask for 0~n Number on interval , Now all we have is the number of digits , To do ？
Refer to the idea of tree arrays , For example 324 The number of , First seek dp[3][0]+dp[3][1]+dp[3][2]; In this way, less than 300 All of them have been worked out , And then ask dp[2][0]+dp[2][1], This way <320 All of them can be found out , It can be seen as holding down a number from the high position to keep it unchanged, and then changing the value of the low position . This problem is solved according to binary system , Then check whether the high position is continuous when required 1, If yes, this dp Value cannot be added
Post a code ：

int dp[40][2];
int digit[40];
int check(int *p,int size)
{
    
    for(int i=1;i<size;i++)
    {
    
        if(p[i]==1&&p[i-1]==1)
        {
    
            return 0;
        }
    }
    return 1;
}
int findIntegers(int n)
{
    
    for(int i=0;i<40;i++)
    {
    
        dp[i][0]=0;
        dp[i][1]=0;
        digit[i]=0;
    }
    dp[1][1]=1;
    dp[1][0]=1;
    for(int i=2;i<40;i++)
    {
    
        dp[i][0]=dp[i-1][0]+dp[i-1][1];
        dp[i][1]=dp[i-1][0];
    }

    int end=39;
    int start;
    int flag=1;
    for(start=end;n!=0;start--)
    {
    
        digit[start]=n%2;
        n=n/2;
        if(start<39&&digit[start+1]==1&&digit[start]==1)
            flag=0;
    }
    start++;
    int ans=0;
    int len=end-start+1;
    int init=start;
    for(int i=start;i<=end;i++)
    {
    
        for(int j=0;j<digit[i];j++)
        {
    
            if(check(&digit[init],i-init))
             ans+=dp[(end-i)+1][j];
      // ans+=dp[(end-i)+1][1];
        }
    }
    return ans+flag;
}