Approach Summary
dp[i] = dp[i >> 1] + (i & 1). The number of 1-bits in i is same as i/2 plus the last bit.
How to Recognize This Pattern
- Count set bits for all numbers 0..n
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
DP Bit Manipulation