Best DP ever with detailed explanation


  • 0
    A

    public class Solution {
    public int[] countBits(int num) {

        // The original solution without DP, which is a simple bit trick that x&(x-1) eliminates the last bit 1 of x.
        /**
        int[] res = new int[num+1];
        for(int i = 0; i < num + 1; i++) {
            int cnt = 0;
            int x = i;
            while(x > 0) {
                x &= (x-1);
                cnt++;
            }
            res[i] = cnt;
        }
        return res;
        **/
        
        int[] dp = new int[num+1];
        for(int i = 1; i < num + 1; i++) {
            dp[i] = dp[i&(i-1)] + 1;
        }
        return dp;
        
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.