動機

在奇偶性上做dp

Problem

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

 

Example 1:

Input: n = 2Output: [0,1,1]Explanation:0 --> 01 --> 12 --> 10

Example 2:

Input: n = 5Output: [0,1,1,2,1,2]Explanation:0 --> 01 --> 12 --> 103 --> 114 --> 1005 --> 101

 

Constraints:

  • 0 <= n <= 105

 

Follow up:

  • It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
  • Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Sol

數字可以分成奇偶， 如果是奇會變成2x+1這樣就是取x的總數加1 如果是偶會變成2x這樣就是取x的總數

dp的index就是要追縱的目標(數字)，會顯示出input的資料是如何做遞迴的 而dp的結果也要能遞迴，能一次又一次累積上去 最後操縱dp值與index的就是動作

dp = {}
dp[1] = 1
dp[2] = 1
dp[0] = 0
def f(n):
    if n not in dp:
        if n%2 == 0:
            dp[n] = f(n/2)
        else:
            dp[n] = f((n-1)/2) + 1
    return dp[n]
class Solution:
    def countBits(self, num: int) -> List[int]:
        ans = []
        for n in range(0,num+1):
            ans.append(f(n))
        return ans