Tóm tắt đề bài

Nhận xét đầu tiên: về mặt tính toán, đây là một bài toán số lớn và cần cài đặt Big Integer hoặc dùng Java, Python để lập trình.

Đường đi trong bảng là sự kết hợp của dạng đường đi cơ bản sau:

Từ đó, ta có thể sử dụng Dynamic Programming để giải quyết bài toán như sau:

• Gọi ~dp[i][type]~ là giá trị lớn nhất khi di chuyển trong bảng gồm ~i~ cột đầu tiên và kết thúc bằng đường đi dạng ~type~ với ~type \in \{1, 2\}~

• Cơ sở quy hoạch động:

  • ~dp[0][1] = -\infty~.

  • ~dp[0][2] = 0~.

• Công thức truy hồi:

  • ~dp[i][type] = max(dp[j - 1][2 - type] * 2^{3(i - j + 1)} + cost_{type}[j][i])~ với ~1 \le j \le i~.

  • Với ~cost_{type}[j][i]~ là giá trị khi di chuyển theo đường đi dạng ~type~ trong cột ~[j..i]~.

• Đáp án bài toán là ~max(dp[n][1], dp[n][2])~.

Mã nguồn tham khảo