Bài giảng Thiết kế và Phân tích thuật toán_Chương 5: Phương pháp Quy Hoạch Động

Cho số tự nhiên n<=100. hãy cho 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 chỉ tính là một cách. Để 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 va đế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 vì khi số cách phân tích tương đối lớn, phương pháp liệu kê tỏ ra khá chậm