POJ 1953 继续体会DP的内涵

本题就是让你输出N位的二进制数中不包含两个连续的1的个数

DP瞬秒！！！

关键是找到DP方程

假设二进制序列为a1,a2,a3,........a(i-2),a(i-1),a(i)

opt[i]表示i位二进制数中符合上述特性的数字个数

则可得到opt[i]=opt[i-1]+opt[i-2]

因为，

如果a(i)为0，则，opt[i]=opt[i-1]

如果a(i)为1，那么a(i-1)一定为0，则，opt[i]=opt[i-2]

动态规划的题目关键就是找到合适的状态转移方程

#include<stdio.h>
int opt[50];
int binary[10];
void decimal_to_binary(int value)
{
    int _i;
    int cnt=0;
    while(value)
    {
        binary[cnt++]=value%2;
        value=value/2;
    }
    binary[cnt]=9;//indicate the num is end
}
int judge()
{
    int _i;
    for(_i=1;binary[_i]!=9;_i++)
    {
        if(binary[_i-1]==1&&binary[_i]==1) return 0;
    }
    return 1;
}
int main()
{
    int n;
    int cache;
    int i,j;
    int cnt=1;
    //freopen("input","r",stdin);
    opt[1]=2;opt[2]=3;
    for(i=3;i<46;i++)
        opt[i]=opt[i-1]+opt[i-2];
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&cache);
        printf("Scenario #%d:/n%d/n/n",cnt++,opt[cache]);
    }
    return 0;
}