Leetcode -- 338. Counting Bits(DP)

338. Counting Bits(DP)
medium
https://leetcode.com/problems/counting-bits/

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

思路： use dp, find the relation that dp[i] = dp[i-offset] + 1, offset: 0,1,2,4,8..
          eg dp[4] = d[4-4]+1 = 1, dp[6] = dp[6-4] + 1 = dp[2] + 1 = 2
Complexity:  time-O(N), SpaceO(N)

public class Solution {
    public int[] countBits(int num) {
        int[] dp = new int[num + 1];
        int offset = 1;
        dp[0] = 0;
        for(int i = 1; i <= num; i++){
            if(offset * 2 == i) offset = i;
            dp[i] = dp[i - offset] + 1;
        }
        return dp;
    }
}