Nếu gọi \(F[i][x]\) là số dãy nhị phân độ dài \(i\) và kết thúc là \(x\). Ta có công thức QHĐ:

\(F[i][x] = F[i-1][1 - x] + \sum F[j][x]\ \forall i - j \le k, j < i\).

Từ công thức trên ta thấy rằng chỉ cần 1 mảng 1 chiều \(F[i]\) là đủ :

\(F[i] = F[i-1] + \sum F[j] \ \forall i - j <= k\).

Nhưng độ phức tạp của thuật toán là \(O(n * k)\).

Ta đặt \(s = \sum F[j][x]\ \forall i - j \le k, j < i\)
khi chuyển từ \(i \rightarrow i+1\) thì \(s = s + F[i] - F[i-k]\).

Độ phức tạp thuật toán là \(O(n)\).

Nguồn: https://cowboycoder.tech/