二进制位暴力枚举

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

// 求x在二进制中第k位是0还是1
inline int get(int x, int k)
{
    return x >> k & 1;  // 向前移k位，再与1，1则return 1
}

int main()
{
    int cnt = 0;
    for (int i = 0; i < (1 << 30); i++)  // i<2^30，<<优先级大于<，不必加括号
    {
        bool flag = true;

        for (int j = 1; j < 30; j++)  // 第j位，注意从1开始，因为下面j-1
        {
            if (get(i, j) && get(i, j - 1))  // 如果连续两位都是1，达咩
            {
                flag = false;
                break;
            }
        }
        cnt += flag;
    }
    cout << cnt;
    return 0;
}

DP

/*
状态转移：长度为i，最后一位为0或1
所以存在两种情况，0和1
f[i][0] = f[i-1][0] + f[i-1][1];  第i位不是0，所以i-1可以是1或0
f[i][1] = f[i-1][0];  第i位是1，所以i-1只能是0
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int f[40][2];

int main()
{
    f[0][0] = 1;
    f[0][1] = 0;

    for (int i = 1; i <= 30; i++)
    {
        f[i][0] = f[i - 1][0] + f[i - 1][1];
        f[i][1] = f[i - 1][0];
    }

    cout << f[30][0] + f[30][1];  // 要输出两种情况
    return 0;
}