Chào tất cả mọi người, mình có một bài về quy hoạch động như thế này nhưng khổ nỗi đã nghĩ mấy ngày mà vẫn chưa nghĩ ra. Mình cũng thử “google” nhưng cũng không tìm thấy bất kỳ trang nào liên quan cả. Các bạn ai có ý tưởng gì về bài này (cơ sở quy hoạch động, công thức truy hồi,…) chỉ mình với. Đề bài như sau:
Xét bảng H kích thước 4x4, các hàng và các cột được đánh chỉ số A, B, C, D. Trên 16 ô của bảng H, mỗi ô ghi một kí tự thuộc tập {A, B, C, D}.
Cho xâu S gồm n ký tự chỉ gồm các chữ lấy từ tập {A, B, C, D}. Xét phép co R(i): thay ký tự S[i] và S[i+1] bởi kí tự H[S[i], S[i+1]].
Ví dụ: Với S=“ABCD”, khi áp dụng liên tiếp phép co R(1) sẽ được ABCD->ACD->BD->B.
Cho trước ký tự X thuộc về {A, B, C, D}. Hãy tìm ra một dãy n-1 phép co để ký tự còn lại cuối cùng trong S là X
Mong nhận được sự giúp đỡ từ mọi người 
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?