Mình cmt để hóng nha.

Bài này vẽ hình ra thì mới hình dung đc, cơ mà ở đây mình ko tiện có cái gì để vẽ nên nói bằng chữ vậy :v

Quan sát:

• Xét 1 đường đi bất kỳ trên bảng
• Cắt bảng ở cột i bất kỳ
• Sau khi cắt, đường đi có thể trở thành 1 trong 2 loại:
  • 1 đường đi, có 1 đầu thò ra ở cột i (ở hàng 1 / 2 / 3)
  • 2 đường đi phân biệt, 1 đường xuất phát từ (1, 1) và có 1 đầu thò ra, 1 đường đi có 2 đầu thò ra. Chú ý về sau 2 đường đi này sẽ phải được nối làm 1.

Như vậy, ta có thể quy hoạch động với tập trạng thái là (i, state), với i là cột hiện tại, và state = 1..6, thể hiện 1 trong 6 trường hợp trên. Bằng các trạng thái (i, state) ta có thể biểu diễn đầy đủ thông tin về 1 bài toán con chỉ gồm i cột đầu.

Để biết chuyển trạng thái như nào thì phải vẽ chi tiết các trường hợp ra.

Tuy nhiên bài này cần tìm dãy nhị phân lớn nhất nữa, nên chắc là trong trường hợp 2 đường đi phân biệt, cần phải lưu thêm 1 chiều thể hiện độ dài của đường đi thứ nhất.

Đến đây thì mình có công thức như sau:

• f(i, state) = dãy bit lớn nhất xây dựng được, nếu đến cột i, có 1 đầu thò ra (vị trí thò ra thể hiện bởi state)
• g(i, state, len) = (a, b) với a, b lần lượt là 2 dãy bit của 2 đường đi, nếu đến cột i, có 2 đường đi thò ra, đường đi 1 có độ dài là len.