Tìm tổng số nguyên lớn nhất trên đường đi tìm được

[Vi_Doan (Doan Vi)]

Bác nào giúp mình làm bài này với. Sắp dealine mà mình không làm đươc.
Cho một ma trận gồm n hàng và m cột được đánh số từ trên xuống dưới,
từ trái qua phải, mỗi ô trên ma trận là một số ngẫu nhiên có giá trị
tuyệt đối không vượt quá 10^9. Từ vị trí phía trên bên trái, hãy tìm
đường đi đến vị trí góc dưới bên phải sao cho đường số ô phải đi qua là
nhỏ nhất (mỗi nước đi chỉ đi đến ô có một cạnh chung). Trong các cách
đó, tìm cách đi sao cho tổng giá trị các ô trên đường đi là lớn nhất.
Input
Dòng đầu tiên là 2 số nguyên n, m (n, m<=2x10^3).
Dòng thứ i trong n dòng tiếp theo gồm m số nguyên cách nhau một
khoảng trắng. Giá trị thứ j tại dòng i tương ứng với giá trị aij trong
ma trận(|a|<=10^9).
Output
Một số nguyên duy nhất là tổng lớn nhất trên đường đi tìm được.
Example
Input:
3 3
1 2 3
-1 5 6
0 2 9

Output:
23
Thuật toán được giải bằng ngôn ngữ C#

[Gio (Gió)]

Qhd với công thức
F[i,j]=

• F[i,j-1]+A[i,j] nếu i=1
• F[i-1,j]+A[i,j] nếu j=1
• max(F[i-1,j],F[i,j-1])+A[i,j]

Kq bài toán = F[n,n]

Với i,j từ 1 đến n
update: xin lỗi vì công thức trước viết vội nên thiếu cụ thể bảng F sau khi tính:
1 3 6
0 8 14
0 10 23

[Vi_Doan (Doan Vi)]

Cụ thể hơn được không bạn

[Tulip (lx)]

bài này hơi giống bài hôm nọ mình test vccorp. cách giải tương tự nhau luôn.

Đề bạn viết thiếu rõ ràng quá, nếu vẽ 1 cái đồ thị sẽ dễ nhìn hơn nhiều. Diễn đàn ko khuyến khích cách giải bài tập, cơ àm mình cứ đưa ra hướng đi thuật toán vậy. Nó cũng là thuật tóa của bạn @gio nói ở trên, mình minh họa bằng hình ảnh cho dễ vậy:

1 2 3 -> 1 2 3
1 5 6 1 5 15
0 2 9 0 11

Do vậy nếu đường đi từ A33 -> A22 thì sẽ chọn đường đi là A33->A23->A22. Chạy hết toàn bộ các hàng/cột từ dưới lên trên, phải sang trái.

Hình như có nhầm 1 chút nhưng đại khái cách giải là như vậy :D.