leetcode_338

Golang:

思路：这题以DP为思路，不算很难，以9为例，arr[9]=arr[8]+arr[9-8]，arr[23]=arr[16]+arr[23-16]

代码如下：

func countBits(num int) []int {
    if num==0 {
        return []int{0}
    }
    if num==1 {
        return []int{0,1}
    }
    arr:=make([]int,num+1)
    arr[0],arr[1],arr[2]=0,1,1
    i:=2
    for arr[num]==0 {
        temp,j:=i,i+1
        i*=2
        for j<i&&j<=num{
            arr[j]=arr[j-temp]+arr[temp]
            j++
        }
        if i<=num {
            arr[i]=1
        }
    }
    return arr
}

有疑问加站长微信联系（非本文作者）