A数位dp

奈斯，一晚上学会个数位dp还不错嘿嘿
如题：
600. 不含连续1的非负整数
给定一个正整数 n ，返回范围在 [0, n] 都非负整数中，其二进制表示不包含 连续的 1 的个数。
就是dp[i][j]表示i位数以j开头，一共有多少种数。
这样的话dp[i][j]=dp[i-1][k](按照权求和）
然后题目里面可能会有乱七八糟的规则，比如说连续1，不连续1，不含有某个数…等等；这个时候只要改变dp数组就可以，但是注意，这里面的dp仅仅是初始化。
如果是求0~n区间上的数，现在有的只是多少位数的值，咋办？
参考树状数组那个思想，就是比如说324这个数，先求dp[3][0]+dp[3][1]+dp[3][2];这样就把小于300的都求出来了，然后再求dp[2][0]+dp[2][1]，这样就把<320的都求出来，可以看成是从高位先按住一个数让他不变然后改变低位的数值。这个题就按照二进制那样求就行，然后需要求的时候注意检查高位有没有连续1，有的话这个dp值不能加
贴个代码：

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;
}