600. 不含连续1的非负整数.md

600. 不含连续1的非负整数

版本1：

class Solution {
    boolean[] dp;

    public int findIntegers(int n) {
        if (n <= 2) {
            return n + 1;
        }
        // 创建一个数组，保存每个数是否有连续的1
        int max = Math.max(3, n >> 1);
        dp = new boolean[max + 1];
        dp[0] = false;
        dp[1] = false;
        dp[2] = false;
        dp[3] = true;

        int res = 3;
        boolean flag = false;
        for (int i = 4; i <= n; i++) {
            flag = isConsecutiveOne(i);
            if (i <= max) {
                dp[i] = flag;
            }
            res = res + (flag ? 0 : 1);
        }
        return res;
    }

    public boolean isConsecutiveOne(int n) {
        boolean flag = false;
        if (n % 2 == 0) {
            flag = dp[n >> 1];
        } else {
            int tmp = n >> 1;
            if (tmp % 2 != 0) {
                flag = true;
            } else {
                flag = dp[tmp >> 1];
            }
        }
        return flag;
    }
}