leetcode 600. Non-negative Integers without Consecutive Ones非負の整数連続1+DPダイナミックプランニングを含まない

Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.
Example 1: Input: 5 Output: 5 Explanation: Here are the non-negative integers <= 5 with their corresponding binary representations: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. Note: 1 <= n <= 109
問題の意味は簡単だが、やるのは本当に難しい.明らかに直接暴力で解くのはタイムアウトに違いない.これはDPでできると思っているが、プッシュ式の導きはしないので、ネットで答えを探すしかない.
この文字列の長さのバイナリ数をすべて連続していない1の数字の個数を計算し、最後から2番目の文字からこのバイナリ数の文字列を巡回します.現在の文字と後ろの位置の文字が1であれば、私たちが何も計算していないことを示しています.分からないのは例を持って見ることができます.現在の文字と後の位置の文字が0であれば、前に挙げた100という例のように、101という状況を多く計算したことを示します.私たちはどのように多くの状況を確定しますか?もし私たちに与えられた数字が8で、バイナリが1000であれば、私たちはまず長さ4ですべての状況を計算して、合計8種類です.十進法から二進文字列への書き方をよく見ると、変換結果は実際の二進数と反転していることがわかります.だから、私たちのtは「0001」です.では、逆数の2番目から前に回ります.i=1になると、2つの連続した0が現れます.では、i=1という位置に1が現れる回数はone配列にあります.では、1を減らします.減算すると0101ということになりますが、さらに進むと、i=0の場合、また2つの連続0が発見され、i=0という位置で1の回数をone配列に出すことができます.私たちは1を減算し、1001を減算します.
主にこのチュートリアル[LeetCode]Non-negative Integers without Consecutive Ones非負の整数は連続する1を含まない
コードは次のとおりです.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

class Solution 
{
public:
    int findIntegers(int num)
    {
        int n = num;
        string t = "";
        while (n > 0)
        {
            t += (n & 1) == 1 ? "1" : "0";
            n = n >> 1;
        }

        vector<int> zero(t.length() , 0), one(t.length(), 0);
        zero[0] = one[0] = 1;
        for (int i = 1; i < t.length(); i++)
        {
            zero[i] = zero[i - 1] + one[i -1];
            one[i] = zero[i - 1];
        }

        int res = zero[t.length() - 1] + one[t.length() - 1];
        for (int i = t.length() - 2; i >= 0; i--)
        {
            if (t[i] == '1' && t[i + 1] == '1')
                break;
            if (t[i] == '0' && t[i + 1] == '0')
                res -= one[i];
        }
        return res;
    }
};