Đếm số dãy nhị phân độ dài N không chứa k bit 1 liên tiếp

[Nobita004 (Kirito-kun)]

Đếm xem có bao nhiêu xâu nhị phân độ dài N không chứa k bit 1 liên tiếp. Cho em xin thuật toán QHĐ được không ạ!

Với lại nếu ai có quyển sách hoặc trang nào hay viết về quy hoạch động thì cho em xin với! Em cảm ơn rất nhiều !

[Dao_Thanh_Loc]

bài này mình nghĩ bạn nên sinh nhị phân và viết 1 hàm con kiểu tra

[Nobita004 (Kirito-kun)]

Nhưng N<=10^3 bạn ơi!

[rogp10]

Không có k bit 1 liên tiếp => giữa 2 bit 0 chỉ có từ 0 đến k-1 bit 1 => ??? => profit