Ha Hoang's Blog

Loạt bài Quy hoạch động cơ bản mình trình bày ở đây nhằm mục đích định rõ các bước tư duy cụ thể để đưa ra được thuật toán Quy hoạch động cho một bài toán. Sản phẩm của quá trình lập luận, suy nghĩ gồm có: định nghĩa hàm trạng thái mô tả một trạng thái chung của bài toán; một công thức Quy hoạch động thể hiện việc tính toán các trạng thái sau nhờ một vài trạng thái trước đó; một số bài toán cơ sở làm tiền đề cho việc tính các trạng thái sau và một phương án lưu trữ giá trị các trạng thái nhằm mục đích đưa ra kết quả cuối cùng hoặc truy vết tìm một phương án hợp lí. Bài này sẽ bàn về một bài Quy hoạch động điển hình "Dãy con tăng dài nhất" . Có thể bạn đã đọc, thấy bài này ở nhiều nơi rồi, ở bài viết này mình một lần nữa phân tích theo 5 bước cụ thể để các bạn mới học có thể tiếp cận một cách dễ dàng hơn. Tóm tắt bài Dãy con tăng dài nhất (LIQ) : Cho dãy gồm N phần tử a[i] với i từ 1 tới N; Hãy tính độ dài của dãy con tăng đơn điệu dài nhất. Một dãy con tăng đơn điệu là một dã...

Frog2 là một bài tập Quy hoạch động cơ bản dạng dễ . Bài này được nằm trong loạt bài mẫu nhằm giúp các bạn định hướng cách nghĩ để có thể đưa ra một thuật toán Quy hoạch động . Ở đó bao gồm các bước tư duy nhằm định nghĩa một hàm Quy hoạch động (hàm trạng thái), một công thức Quy hoạch động, các bài toán cơ sở, bảng phương án và các lưu ý khi tính bảng phương án. Bài Frog 2 có thể tóm tắt như sau: Có N hòn đá được đánh số từ 1 tới N. Hòn đá thứ i có độ cao h_i. Ban đầu chú ếch ở hòn đá 1. Chú liên tục thực hiện một loạt hành động sau: Nếu chú đang ở hòn đá i, chú có thể nhảy tới các hòn đá i+1, i+2,..., i+K và chi phí cho bước nhảy đó là |H_i - H_j| với j là hòn đá mà chú ếch nhảy tới. Hỏi chi phí tối thiểu để chú ếch nhảy từ hòn đá đầu đến hòn đá thứ N? Nếu đã làm bài Frog 1 rồi thì bạn sẽ nhận thấy ngay Frog 2 là bài khá tương tự bài Frog 1. Như vậy, cách nghĩ và cách phân tích để đưa ra phương án Quy hoạch động cũng tương tự bài Frog 1. Bạn có thể thực hành nghĩ lại theo các chỉ dẫ...

Theo kinh nghiệm dạy học của cá nhân mình, các chiến lược thiết kế thuật toán là những nội dung nâng cao, là các nội dung khó đối với nhiều giáo viên cũng như học sinh.  Giả sử giai đoạn lập trình cơ bản, các học sinh có khả năng sử dụng ngôn ngữ lập trình nào đó để biểu diễn các thuật toán cơ bản tốt rồi, học sinh có thể vận dụng tư duy để đưa ra thuật toán cho các bài toán cơ bản rồi. Vậy mà khi chuyển qua nội dung các chuyên đề nâng cao là đa số học sinh bị tụt lại 😆 Và trên thực tế, số lượng này không hề nhỏ. Vậy điều gì làm cho nội dung này là một nội dung quá khó, không thể học được với nhiều học sinh? Đối với các học sinh giỏi về Quy hoạch động, chắc là các HS đội tuyển Quốc Gia, Quốc Tế thì họ nghĩ thế nào về chủ đề này? Người ta có thấy chủ đề này "dễ" ngay từ đầu không? Và con đường để họ giỏi về nội dung này là gì? Nếu mình theo con đường đó, mình có giỏi được như họ không? Hihi, câu trả lời tôi nghĩ sẽ rất chung chung, đại khái là đọc sách chuyên đề QHĐ, đại khái...