Xin ý tưởng giái thuật tìm đường dài nhất trong ma trận 2 chiều

#1

Chào mọi người, như tiêu đề mọi người cho e xin ý tưởng giải bài. E xin nói cụ thể bài toán thế này ạ
Cho 1 ma trận M x N. Tìm 1 đường gấp khúc bắt đầu từ hàng 1 và kết thúc tại hàng cuối cùng sao cho tổng các phần tử mà đường đi qua là lớn nhất và đi theo quy tắc sau:

  • Từ ô ở hàng trên chỉ đi thẳng đứng xuống dưới, hoặc chéo sang trái 1 ô hoặc chéo sang phải 1 ô.
    Cụ thể, chẳng hạn đang ở ô [x, y] thì được đi xuống ô [x+1,y] hoặc [x+1,y+1] hoặc [x+1,y-1].
    Bác nào biết xin chỉ giáo
    E xin cảm ơn trước :slight_smile:
#2

Bài này QHĐ cơ bản mà bạn, vì để max 1 ô thì bạn phải max hết những ô dẫn đến nó đã.

#3

Cho chạy thử tất cả các trường hợp, cái nào dài nhất thì trả về.

#4

A nói cụ thể giúp e được không ạ?

#5

Nếu làm vậy với những bài có M, N lớn sẽ không làm được và nó cũng k phải giải thuật nữa ạ

#6

Để giải bài bằng QHĐ thì bài toán phải có thể chia nhỏ và lời giải của bài toán lớn là sự kết hợp lời giải (tối ưu) của những bài toán con. Có hai dạng là tổ hợp (combinatoric) và tối ưu.

Có thể thấy để đi đến ô nào đó, ví dụ như ô (3, 2) thì chỉ có thể đi từ 3 ô xuống: (2, 1); (2, 2); (2, 3). Vậy vấn đề trở thành tìm đường đến những ô này dài nhất.

1 Like
#7

Ok r ạ, e cám ơn a!
…

#8

Bạn có thể thấy là với mỗi ô A chỉ có tối đa 3 cách để đi ô tiếp theo. Như vậy độ phức tạp của thuật toán nhỏ hơn O(m x n^3), chỉ là bậc 4 thôi mà :))

#9

Nhưng QHĐ là O(m*n) nhé :smiley: và chỉ cần lưu 2 dòng.

1 Like
#10

Ô :))

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?