Cho số tự nhiên n | Generated by Foxit PDF Creator Foxit Software http For evaluation only. Chương 5 Phương pháp qui hoạch động 1. CÔNG THỨC TRUY HÒI I. VÍ DỤ Chớ Sở tư nhiên n 100. Hãy chớ biết cỏ bao nhiêu cách phân tích số n thánh tổng của dãy các số nguyên dương các cách phân tích là hoán vị của nhau chi tỉnh là một cách. Ví dụ n - ĩ có 7 cách phàn tích 1. 5 1 1 1 1 1 2. 5 l l l 2 3. 5 l l 3 4. 5 1 2 2 5. 5 1 4 6. 5 2 3 7. 5 5 Lưu ỷ n 0 vẫn Cỡi là cỏ 1 cách phân tích thành tẳng các sổ nguyên dương 0 là tống của dãy rỗng Đe giải bài toán này trong chuyên mục trước ta đà dùng phương pháp liệt kê tất cả các cách phân tích và đếm số cấu hình. Bây giờ ta thử nghĩ xem có cách nào tính ngay ra số lượng các cách phân tích mà không cần phải liệt kê hay không . Bởi vi khi số cách phân tích tương đối lớn phương pháp liệt kê tô ra khá chậm n 100 có 190569292 cách phân tích . Generated by Foxit PDF Creator Foxit Software http For evaluation only. Nhận xét Nếu gọi F m v là số cách phân tích số V thành tống các số nguyên dương in Khi đó Các cách phân tích số V thành tong các sả nguyên dương m có thể chia làm hai loại Loại l Không chứa số m trong phép phân tích khi đó số cách phân tích loại này chính là số cách phân tích sả V thành tong các số nguyên dương m tức là so cách phân tích số V thành tổng các số nguyên dương m -1 và bang F m -1 v . Loại 2 Có chứa ít nhất một số m trong phép phân tích. Khi đó nếu trong các cách phân tích loại này ta bỏ đi so m đó thi ta sè được các cách phân tích so V - m thành tổng các sả nguyên dương m Lưu ý điều này chì đúng khi không tinh lặp lại các hoán vị của một cách . Có nghĩa là về mặt sả lượng số các cách phân tích loại này bằng F m V - m Trong trường hợp m V thì rò ràng chỉ có các cách phân tích loại 1 còn trong trường hợp m V thì sẽ có cả các cách phẫn tích loại 1 và loại 2. Vi thế F m v - F m -1 v nếu m V F m v F m-l v F m v-m nếum v Ta có công thức xây dựng F m v từ F m - 1 v và F m V - m . Công thức này có tên .
