Có cách nào để hiểu và làm được những bài liên quan đến Quy hoạch động không các bác ?
E đọc cuốn GT và LT của thầy Hoàng mà phần đó khó quá !! -_-
Có cách nào để hiểu và làm được những bài liên quan đến Quy hoạch động không?
Đó là cả một nghệ thuật đấy bạn 
3 Likes
học hỏi nghệ thuật đâu phải là xấu đâu anh 
cày nhiều là được.
vào đây rồi đọc và làm bài từ trên xuống dưới.
5 Likes
Để hiểu QHD, bạn phải hiểu QHD giải quyết vde gì đã.
Lấy ví dụ cơ bản nhất mà ai cũng biết đó là tính số Fibonaci. F(n) = F(n - 1) + F(n - 2)
Nếu ta tính F(5). Khi đó ta phải tính F(4) + F(3)
Mà làm sao tính F(4)? Thì phải tính F(3) + F(2) (tương tự cho F(3))
Như vậy ta thấy rằng F(3) bị tính toán lại 2 lần (xem hình)
Vậy ta thấy n càng cao, thì khi đó sẽ có nhiều số phải tính toán lại. Như F(100) = F(99) + F(98) = F(F98) + F(97) + F(97) + F(96) = F(97) + F(96) + F(96) + F(95) + F(96) + F(95) + F(95) + F(94) … => Tốn kém chi phí. Như Fibo tính toán cộng trừ còn đơn giản. Cứ nghĩ khi mình tính không phải Fibo mà số nào đó mỗi lần tính mất O(n^2) thì xem thời gian sẽ tăng lên kinh khủng như thế nào?
THấy như vậy, ngta mới nghĩ có cách nào để lưu lại giá trị nhwuxng bài toán con đó, và lấy kết quả đó ra mà không phải tính toán quá nhiều hay không? Thì QHD ra đời để giải quyết câu hỏi trên.
Ngắn gọn, QHD là một bài toán chia để trị, nhưng nó có khả năng ghi nhớ giá trị của bài toán con và lấy giá trị đó ra mà không cần phải tính toán lại, nếu có thì cực kỳ ít.
Cách để hiểu các bài toán QHD, là khi học, bạn hãy vẽ cây ra như mình vẽ ở trên Xong tự tìm cách ghi nhớ những bài toán con bị trùng hoặc lặp lại, nếu không được thì hãy đọc sách phần họ ghi nhớ + lấy ra như thế nào. Rồi chạy tay trên cây bạn đã vẽ thì sẽ nhanh nghiệm ra hơn đó. Ngoài ra vẽ cây cũng là một cách giúp bạn xác định bài toán QHD cũng khá nhanh nữa.
10 Likes
e chân thành cảm ơn các bác :))))))))))))))
Ngoài ra còn phải đáp ứng được tính tối ưu từng phần 
Thật ra biến đổi công thức thì dễ (có mấy dạng thôi) chứ tìm công thức mới chua, cả một nghệ thuật
5 Likes
tìm cái công thức truy hồi chắc khoảng hơn 1 nửa time làm bài :))
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?