Mô phỏng thuật toán Đếm bit 0..n (DP)

Counting Bits (DP) · Nhóm: Bit & Mặt nạ

Đếm số bit 1 của mọi số 0..n bằng quy hoạch động: bits[i] = bits[i>>1] + (i&1), vì bỏ bit thấp nhất chính là chia đôi và bài toán con đã tính trước.

Ý tưởng

Khởi tạo bits[0] = 0 làm ô neo (số 0 không có bit 1 nào).

Duyệt i từ 1 tới n, đặt bits[i] = bits[i>>1] + (i&1).

Vì i>>1 luôn nhỏ hơn i nên giá trị nguồn đã sẵn sàng, mỗi ô chỉ tính một lần.

Vì sao đúng

Bỏ bit thấp nhất của i cho ra i>>1 (đã biết số bit), chỉ cần cộng thêm bit lẻ i&1; nhờ tái dùng kết quả cũ, toàn bộ dãy tính trong O(n) thay vì đếm bit từng số riêng lẻ.

Mã Python

def count_bits(n):
    bits = [0] * (n + 1)          # bits[i] = number of 1s in i
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)  # drop lowest bit -> half
    return bits

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.