1. Dạng 1:
- Đi từ điểm [1,1] đến [m,n]:
(Đi từ ô đầu tiên đến ô cuối cùng của mảng 02 chiều)
- Yêu cầu: Tổng giá trị tại vị trí ô [i,j] là lớn nhất (nhỏ nhất)
- Quy luật di chuyển:
Từ ô [1,1], đi theo hướng xuống dưới hoặc sang phải đến ô cuối cùng [m,n]
A[i,j]
(
A[i,j+1]

(



A[i+1,j]



Ví dụ:
Duongdi.inp
Duongdi.out


Giá trị Max
Giá trị Min

3 3
12 11 15
4 6 9
-12 25 -4
50
12 11 6 25 -4
25
12 4 -12 25 -4


Thuật toán
Gọi F[i,j] là giá trị lớn (nhỏ) nhất của cách đi theo quy luật đến ô [i,j]
Theo cách đi (đi từ ô đầu tiên [1,1]) nên ta có: F[1,1]:=A[1,1]
Để đạt được giá trị F[i,j] ta cần xét theo yêu cầu:
+ Lớn nhất:
F[i,j]:=F[i,j-1] + A[i,j] nếu F[i,j-1] > F[i-1,j]
(đi từ ô [i,j-1] đến ô [i,j]: đi sang phải)
Ngoài ra:
F[i,j]:=F[i-1,j] + A[i,j] (trường hợp F[i-1,j] > F[i,j-1])
(đi từ ô [i-1,j] đến ô [i,j]: đi xuống dưới)
+ Nhỏ nhất:
F[i,j]:=F[i,j-1] + A[i,j] nếu F[i,j-1] < F[i-1,j]
(đi từ ô [i,j-1] đến ô [i,j]: đi sang phải)
Ngoài ra:
F[i,j]:=F[i-1,j] + A[i,j] (trường hợp F[i-1,j] < F[i,j-1])
(đi từ ô [i-1,j] đến ô [i,j]: đi xuống dưới)
(Trường hợp F[i,j-1] = F[i-1,j] , đi theo cách nào cũng được)
Công thức QHĐ tổng quát chung lại cho 2 trường hợp:
F[i,j]:=MAX(F[i,j-1], F[i-1,j]) + A[i,j] (cho bài toán tìm MAX)
F[i,j]:=MIN(F[i,j-1], F[i-1,j]) + A[i,j] (cho bài toán tìm MIN)
Truy vết (Xuất đường đi)
Gọi Đệ quy
+ Xét giá trị F[i,j] tại ô [i,j] nếu trước đó đi từ ô [i-1,j], tức là đi từ ô bên trên xuống, ngược lại nếu nếu trước đó đi từ ô [i,j-1], tức là đi từ ô bên trái sang. Khi đó ta xác định được đường đi theo yêu cầu của bài toán.
+ Với trường hợp chung tại ô [i,j] ta có bài toán tổng quát nếu xét từ ô đích [m,n] ta sẽ lần ngược về ô ban đầu [1,1].
+ Thuật toán gọi Đệ quy:
Procedure Truyvet(i,j:Integer);
Begin
If F[i,j]=F[i-1,j] + A[i,j] then Dec(i)
Else
Dec(j);
If (i>0) and (j>0) then
Begin
Truyvet(i,j);
Write(f,A[i,j],` `); {Nếu xuất giá trị ra tệp}
End;
End;
* Lưu ý: Khi thực hiện gọi Đệ quy: Truyvet(m,n) chỉ xuất đường đi từ ô ban đầu [1,1] đến trước ô [m,n], do đó ta cần phải xuất thêm giá trị (vị trí) của ô [m,n].
Khử Đệ quy
+ Thực hiện truy vết theo cách dò