Link đến trang bài tập

Thuật toán:

Trước tiên chúng ta nhận xét rằng độ dài của dãy không bao giờ vượt quá . Lý do là bởi vì các khác nhau từng đôi một và do . Vì các dãy là không giao nhau nên nếu đặt là độ dài của dãy thứ ta có .

Ta tính toán giá trị qui hoạch động sau: - số dãy thỏa mãn điều kiện và giá trị của phần tử lớn nhất bé hơn (chặn trên của dãy). Công thức qui hoạch động dưới đây cho phép chúng ta thiết lập số cách khác nhau khi thiết lập độ dài của dãy. Nó có thể tính đơn giản như sau:

• cơ sở

Chúng ta có thể tính toán công thức qui hoạch động trên với chi phí bộ nhớ (tuy nhiên nếu để mảng chiều cũng chấp nhận được). Chú ý rằng sau khi tính sẽ được nhân với (vì ta đã giả thiết , nhưng trên thực tế nó có thể là một hoán vị bất kỳ)

Với giá trị đã cho. Đặt với là các cận trên có thể có.

Vấn đề tiếp theo là ta tính xem có bao nhiêu cách đặt các khoảng với tổng độ dài len vào trong đoạn độ dài .

Đặt ta có phương trình (*)

Do vậy mỗi giá trị cần phải nhân với số nghiệm của phương trình (*).

Đặt là số nghiệm không âm của phương trình

Ta có thể chọn do đó:

• f[i,j-1]=f[i-1,j-2]+f[i-1,j-3]+\ldots+f[i-1,0]$

Do vậy hay

Do vậy có thể tính mảng trong

Và số nghiệm của phương trìn (*) chính là

Đáp số của bài toán là :