Sử dụng phương pháp quy hoạch động

Gọi:

• \(a[i], b[i], c[i]\) lần lượt là giá trị các ô ở cột \(i\) của dải thứ nhất, thứ hai và thứ ba.
• Đặt \(a[n+1] = 0\), \(b[n+1] = 0\), \(c[n+1] = 0\). Nhảy vào vị trí kết thúc thì không được thêm điểm.
• \(DPg[i]\) là tổng điểm nhận được khi nhảy đến cột \(i\) và đặt chân vào ô ở dải giữa.
• \(DP2b[i]\) là tổng điểm nhận được khi nhảy đến cột \(i\) và đặt chân vào ô không ở dải giữa, tức là ở một trong hai dải thứ nhất hoặc thứ ba.

Quy hoạch động:

• Khởi tạo:
  • \(DPg[0] = 0\)
  • \(DP2b[0] = 0\)
• Lặp từ \(i = 1\) đến \(n + 1\):
  • Gán \(DPg[i]\) giá trị vô cùng nhỏ.
  • Gán \(DP2b[i]\) giá trị vô cùng nhỏ.
  • Lặp từ \(j = 1\) đến \(p\):
    • Nếu \(i - j\) lớn hơn hoặc bằng \(0\):
    • \(DPg[i]\) bằng giá trị lớn nhất giữa \(DPg[i]\) hiện tại và \(DP2b[i - j]\) cộng với \(b[i]\). Đây là trường hợp nhảy vào ô dải giữa cột \(i\).
    • \(DP2b[i]\) bằng giá trị lớn nhất giữa \(DP2b[i]\) hiện tại và \(DPg[i - j]\) cộng với giá trị lớn nhất giữa \(a[i]\) và \(c[i]\). Đây là trường hợp nhảy vào ô dải bên ngoài.

Kết quả cuối cùng:

• Là giá trị lớn nhất giữa \(DPg[n + 1]\) và \(DP2b[n + 1]\).