很简单的一道计数题 给定整数n 求不大于n的正整数中 二进制表示没有连续的1的数字个数
在dp过程中只要保证不出现连续1以及大于n的情况即可。
所以设计按位dp[i][j]表示到第i位 j=0表示第i位为0 且值等于n的情况 2为值小于n的情况
j=1表示第i位为1 且值等于n的情况 3为值小于n的情况
转移方程很简单 看代码吧 这道题应该是Mid难度吧
class Solution {
public:
int findIntegers(int num) {
int va=num;
int dp[40][4];
int f[40];memset(f,0,sizeof(f));
memset(dp,0,sizeof(dp));
int tot=31;
while(va>0)
{
if((va%2)==1)f[tot]=1;
tot--;
va=(va>>1);
}
if(f[tot+1])dp[tot+1][1]=dp[tot+1][2]=1;
else dp[tot+1][0]=1;
for(int i=tot+2;i<=31;i++)
{
if(f[i])
{
dp[i][1]+=dp[i-1][0];
dp[i][2]+=dp[i-1][0]+dp[i-1][2]+dp[i-1][1]+dp[i-1][3];
dp[i][3]+=dp[i-1][2];
}else
{
dp[i][3]+=dp[i-1][2];
dp[i][0]+=dp[i-1][0]+dp[i-1][1];
dp[i][2]+=dp[i-1][2]+dp[i-1][3];
}
}
return dp[31][0]+dp[31][1]+dp[31][2]+dp[31][3];
}
};
第十六周 Leetcode 600. Non-negative Integers without Consecutive Ones(HARD) 计数dp
原文：http://www.cnblogs.com/heisenberg-/p/6978326.html