Phân tích số

Hãy đếm số cách phân tích số N ( N<=100000 ) thành tổng các số nguyên dương.
Lưu ý 2 cách chỉ khác nhau về thứ tự các số hạng được coi là giống nhau. Ví dụ 4 có 5 cách phân tích sau:
4 = 1 + 1 + 1 + 1
4 = 1 + 1 + 2
4 = 1 + 3
4 = 2 + 2
4 = 4

Hai cách phân tích 4 = 1 + 3 = 3 + 1 chỉ được tính một lần.
Vì kết quả sẽ rất lớn nên các bạn chỉ cần đưa ra phần dư của phép chia số cách tìm được cho 1000000000 ( 10^9 ).
Input

Một số tự nhiên N duy nhất.
Output

In ra phần dư của của số cách tìm được cho 10^9.
Example

Input:
4

Output:
5

f[i,j]=f[i-1,j]+f[i,j-a[i]]

Đó là cách cơ bản.Chỉ chạy được các test cơ bản thôi.Bạn cần phải tối ưu từng đoạn code.

Ý anh là sao. Mà cũng công nhận cách đó cơ bản nhất

Với mỗi k thì ta có công thức tính P(k) qua các P(k-1),P(k-2),... rồi; tính xong thì lưu vào một mảng. Với mỗi k thì P(k) liên quan đến các số P(k-1/2i*(3i+/-1)) nghĩa là các số 1/2*i*(3i+/- 1) phải tính đi tính lại nhiều lần nên tính trước các số như vậy và lưu vào mảng để khi nào cần sử dụng thì ko phải tính lại.

Thì tất nhiên là QHD mà .

Quy hoạch động là đúng.Nhưng bạn chưa tối ưu từng đoạn code.

Anh nói kĩ hơn đi. Cái anh nói trên em chả hiểu chi hết

Anh đọc trên [You must be registered and logged in to see this link.]