QHĐ – Đường đi có tổng lớn nhất

1. Đề bài Quy hoạch động Đường đi có tổng lớn nhất

Cho ma trận A hình vuông có kích thước n*n. Đầu tiên bạn ở ô có tọa độ [1,1], bạn được phép đi sang phải và đi xuống dưới ô kề cạnh. Hãy tìm đường đi có tổng lớn nhất khi đi đến ô [n,n].

Input

-Dòng đầu là số nguyên dương N (n<= 1000).

– n dòng tiếp theo, mỗi dòng gồm n số nguyên dương biểu diễn ma trận A.

Output 

– một dòng duy nhất là kết quả bài toán.

Bài này mình viết để các bạn tham khảo một dạng QHĐ cơ bản, nên về dữ liệu mình không yêu cầu A[i,j] có giới hạn bao nhiêu, và nhiều dữ kiện khác.

Ví dụ

Input

4

9 2 3 4

9 0 2 2

9 9 9 2

2 2 9 9

Output

63

2. Hướng dẫn giải bài QHĐ đường đi có tổng lớn nhất

– Gọi F[i,j] là tổng lớn nhất có được khi đi đến ô i,j.

– Khởi tạo F[i,0]=F[0,j]=0;

– Có 2 cách đi đến ô [i,j], một là đi từ trên xuống, hai là từ phải qua, như vậy ta có công thức lần lượt là F[i-1,j] và F[i,j-1]

– Công thức tổng quát F[i,j]=max(F[i-1,j],F[i,j-1])+a[i,j]; (i,j=1..n);

– Kết quả bài toán là F[n,n].

3. Code Quy hoạch động đường đi có tổng lớn nhất