Cần giải thích công thức quy hoạch động

[dukksoocee (catsoougly412)]

Bài toán:

Mỗi thanh sô cô la có dạng thanh dài với kích thước 1 x n đơn vị, trên thanh sô cô la người ta xẻ các rãnh chia thanh sô cô la theo kích thước 1 x 1 cho dễ bẻ. Yêu cầu xác định: Có bao nhiêu cách bẻ thanh sô cô la theo các rãnh đã xẻ thành nhiều phần.
Ví dụ: thanh sô cô la chiều dài n = 3, ta có ba cách bẻ:

• Cách 1: bẻ thành 3 thanh độ dài 1: 1,2,3;
• Cách 2: bẻ thành 2 thanh, một thanh độ dài 2: 1-2 và một thanh độ dài 1 là 3 (cách bẻ 1, 2-3 coi như đã tính);
• Cách 3 là giữ nguyên cả thanh.

Dữ liệu vào: Từ tệp văn bản SUCULA.INP, chứa duy nhất số nguyên n là chiều dài thanh sô cô la.
Dữ liệu ra: Đưa ra tệp văn bản SUCULA.OUT, chứa số cách bẻ tìm được.

Ví dụ:

SUCULA.INP	SUCULA.OUT
3	3

Em đã nghĩ thử nhưng không ra tìm solution thì người ta cho công thức

F[i,j] số cách chia khi thanh có độ dài i và trong cách chia không có thanh lớn hơn j.

F[i,j] = F[i,j-1] + F[i-j,j].

Mọi người có thể giải thích cho em tại s công thức lại như vậy không ạ cảm ơn mọi người
Nghĩ mãi mã không hiểu

[rogp10]

@dukksoocee

F[i,j] là số cách chia khi thanh có độ dài i và trong cách chia không có thanh lớn hơn j.

F[i,j] = F[i,j-1] + F[i-j,j].

Với j chạy từ 1 đến n thì dễ thấy công thức này ko trùng lắp, vì ta sẽ thêm cách chia có thanh độ dài j.
Bài này y như bài cái túi với loại túi 1, 2, 3, …, n.