Sau khi học về đệ quy quay lui, Ngáo thấy rằng thuật toán này rất vui nên liền đưa ra bài toán để cho Duy, Công, Dương, Đạt giải bài toán ấy. Bài toán như sau:

Cho một tam giác vuông có dạng như sau:

1

+ -

1 2 3

+ - + -

1 2 3 4 5

Yêu cầu của Ngáo như sau:

  + Hãy tìm một đường đi từ đỉnh tam giác xuống đáy sao cho giá trị  của biểu thức tạo thành là lớn nhất.

  + Nguyên tắc đi như sau: tại một vị trí nào đó ta chỉ được đi thẳng xuống phía dưới hoặc bên phải ngay dưới nó (mỗi lần chỉ đi đến một ô).

Vd mẫu ở trên có kết quả là: 1 + 2 + 4 = 7.

Dữ liệu vào gồm:

  + Dòng đầu tiên là n cho biết chiều cao tam giác và chiều rộng đáy.

  + n dòng tiếp theo là các phần tử của tam giác.

Dữ liệu ra: Một số duy nhất là đáp án của bài toán.