主題
題目連結：
題目意譯：
給定一正整數 n，回傳範圍 [0, n] 當中，其二進位表示法不包含連續的 1 之數字的數量。
限制：
1 <= n <= 10 ^ 9
範例測資：
範例 1：
輸入： n = 5
輸出： 5
解釋：
以下為 ≦ 5 的非負整數以及它們的二進位表示法：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
在它們當中，只有整數 3 違反規則（有兩個連續的 1）而其他 5 個則符合規則。
範例 2：
輸入： n = 1
輸出： 2
範例 3：
輸入： n = 2
輸出： 3
解題思維：
先定義一個二維陣列 DP[i][j] ，其代表著長度 i 的數字且為 j 開頭（j = 0 或 1）之不含連續 1 的數字數量。
本題動態規劃（Dynamic Programming）的遞迴式很直觀，先設立初始條件
DP[0][0] = 1 、 DP[0][1] = 0
（長度 0 視為一個「0」，這是為了等等方便，而且剛好是「正確的」）
當 i ≠ 0 時，可以看到其為
DP[i][0] = DP[i - 1][0] + DP[i - 1][1] （開頭 0 可以接任何開頭）
DP[i][1] = DP[i - 1][0] （開頭 1 只能接開頭 0）
可以看到這樣，每個長度會包含著一連串 0 開頭的數字。例如 0000 、 00100 等等。但是這等等會很方便。
以 n = 5 為例，其二進位表示法為 "101"。我們從左至右（高位到低位）掃過一次：
101
因為當前位元為 1，而其右有 2 個位元，所以我們可以確定它至少包含了
DP[2][0] + DP[2][1] = 3
個無連續 1 數字。即 "000" 、 "001" 、 "010" 這三個，而這就是為什麼我們需要包含有著前導零的數字們，因為這邊的三個數字全部都是有著前導零的數字。而它們等價於 0 、 1 和 10。
101
因為當前位元為 0，因為無法產生新的貢獻，所以無視。
101
因為當前位元為 1，而其右有 0 個位元，所以我們可以確定它至少包含了
DP[0][0] + DP[0][1] = 1
個無連續 1 數字。而這個比較特殊，其代表是 "100"。因為紅色的「0」右邊沒有東西了，所以只可能有本身這一個數字。而這就是為什麼初始條件是 DP[0][0] = 1 、 DP[0][1] = 0。
最後因為 n 自身就是一個不含連續 1 的數字，所以還需要將其加入所求之中。因此最終所求 ≦ n 的不含連續 1 之數字數量總計為
3 + 1 + 1 = 5 個。
再以 n = 6 為例，其二進位表示法為 "110"。同樣地，從左至右掃過一次：
110
因為當前位元為 1，而其右有 2 個位元，所以我們可以確定它至少包含了
DP[2][0] + DP[2][1] = 3
個無連續 1 數字。即 "000" 、 "001" 、 "010" 這三個。
110
因為當前位元為 1，而其右有 1 個位元，所以我們可以確定它至少包含了
DP[1][0] + DP[1][1] = 2
個無連續 1 數字。即 "100" 、 "101" 這兩個。而因為此時已經將所有可能的組合求出來了，因此可以中斷過程（再繼續只會多加）。
這個現象只要 n 有連續的 1 出現時就會發生，例如 "10110" 、 "1101" 等紅色 1 之位置。因為從該數字之後，不可能再會有新的無連續 1 出現（因為當前就已經違反條件）。
因此最終所求 ≦ n 的不含連續 1 之數字數量總計為
3 + 2 = 5 個。
值得注意的是 n = 6 不符合題意，所以不能算進所求數量中。
而其他 n 值也與上同理。因此只要掃過一次 n 的位數便可以知道所求數量，因此時間複雜度為 O(log n)，但是記得還有預處理的 O(1) 時間。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
