LeetCode 338 Counting Bits - Implementation

DP using previously computed bit counts.

def countBits(n): bits = [0] * (n + 1) for i in range(1, n + 1): bits[i] = bits[i >> 1] + (i & 1) return bits

$O(n)$ time, $O(n)$ space.