Thuật toán chia để trị và quy hoạch động

Có lẽ đa số trong chúng ta sẽ gặp ít nhiều khó khăn khi phải phân biệt thuật toán chia để trị và quy hoạch động (mặc dù vẫn biết cách sử dụng chúng). Điều này cũng không phải là một vấn đề lớn vì cách sử dụng cũng như mục đích sử dụng của…

Thuật toán chia để trị

Thuật toán chia để trị là phương pháp giải một bài toán bằng cách chia nó thành các bài toán nhỏ hơn. Từ kết quả của các bài toán con đó, ta tổng hợp lại để thu được đáp án của bài toán ban đầu. Thông thường, bài toán con được gọi đệ quy từ…

Quy hoạch động

Quy hoạch động (dynamic programing) là phương pháp thường được áp dụng để giải các bài toán toàn cục bằng cách chia chúng thành các bài toán con đơn giản hơn. Đối với dạng bài toán, độ phức tạp thường sẽ là O(n). Tuy nhiên, chúng ta có thể sử dụng một số biện pháp để giảm độ phức…