[LeetCode] 338. Counting Bits

😎풀이

1. dp 배열을 생성한다.
2. i를 n까지 반복한다.
   2-1. 현재 숫자 i를 쉬프트 연산을 통해 마지막 비트를 제거했을 경우 1의 숫자와 마지막 비트가 1인지 판별하여 현재 인덱스에 추가한다.
3. 정답 배열을 반환한다.

function countBits(n: number): number[] {
    const ans: number[] = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
}