bài toán di chuyen quy hoạch động

[nguyentaingoc]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

cho bảng A gồm MxN ô. từ ô (i,j) có thể chuyển sang 3 ô (i+1,j),(i+1,j-1) và (i+1,j+1), hay xác định lộ trinh đi từ hàng 1 đến hàng M sao cho tổng các ô đi qua lớn nhất
công thức
gọi F(i,j) là giá trị lớn nhất có được khi di chuyển đến ô (i,j). có 3 ô có thể đi đến
-F(1,j)=A[1,j]
-F(i,j)=mã(F(i-1,j),F(i-1,j-1),F(i-1,J+1)-A[i,j] với i> 1
mình không hiểu F(1,j)=A[1,j] la thế nào?
các ban viết phần chính giúp minh cũng được

 

[mikelhpdatke]

cho bảng A gồm MxN ô. từ ô (i,j) có thể chuyển sang 3 ô (i+1,j),(i+1,j-1) và (i+1,j+1), hay xác định lộ trinh đi từ hàng 1 đến hàng M sao cho tổng các ô đi qua lớn nhất
công thức
gọi F(i,j) là giá trị lớn nhất có được khi di chuyển đến ô (i,j). có 3 ô có thể đi đến
-F(1,j)=A[1,j]
-F(i,j)=mã(F(i-1,j),F(i-1,j-1),F(i-1,J+1)-A[i,j] với i> 1
mình không hiểu F(1,j)=A[1,j] la thế nào?
các ban viết phần chính giúp minh cũng được

Công nhận là lâu lắm mới động đến dạng QHĐ )
Bây giờ bạn vẽ ra nháp, lưới ô vuông $5*5$ chẳng hạn. Rồi điền các số bất kỳ vào đấy.

gọi F(i,j) là giá trị lớn nhất có được khi di chuyển đến ô (i,j): Tức là đi đến ô A[i,j]. Thì giá trị F[i,j] là lớn nhất có thể trong các cách đi từ hàng đầu đến ô A[i,j]
Vậy, nếu ở ô F[1,j] bất kỳ thì giá trị lớn nhất :F[1,j] khi đi đến ô A[1,j] hiển nhiên là giá trị của ô A[1,j] (Với j từ 1 -> 5).
Giải thích hơi lòng vòng thì phải

Tóm lại: Khi ở hàng 1 F[1,j] = A[1,j] Vì F[1,j] là giá trị lớn nhất khi đi từ hàng đầu đến ô A[1,j]

 

[nguyentaingoc]

Công nhận là lâu lắm mới động đến dạng QHĐ )
Bây giờ bạn vẽ ra nháp, lưới ô vuông $5*5$ chẳng hạn. Rồi điền các số bất kỳ vào đấy.

gọi F(i,j) là giá trị lớn nhất có được khi di chuyển đến ô (i,j): Tức là đi đến ô A[i,j]. Thì giá trị F[i,j] là lớn nhất có thể trong các cách đi từ hàng đầu đến ô A[i,j]
Vậy, nếu ở ô F[1,j] bất kỳ thì giá trị lớn nhất :F[1,j] khi đi đến ô A[1,j] hiển nhiên là giá trị của ô A[1,j] (Với j từ 1 -> 5).
Giải thích hơi lòng vòng thì phải

Tóm lại: Khi ở hàng 1 F[1,j] = A[1,j] Vì F[1,j] là giá trị lớn nhất khi đi từ hàng đầu đến ô A[1,j]

mình chưa hiểu lắm ban viết code giúp minh được không?

 

[11thanhkhoeo]

Từ hàng 1 đến hàng 1 thì chỉ đi qua 1 ô chứ còn gì nữa