โจทย์: กำหนดกริดตัวเลข หา Snake sequence ยาวที่สุด (เคลื่อนที่ขวาหรือลงได้ ถ้าตัวเลขต่างกัน ±1)
ตัวอย่าง: กริด 4×4 → snake ยาว 6: 10(0,0)→9(1,0)→8(1,1)→7(1,2)→6(1,3)→7(2,3)→8(3,3)
อัลกอริทึม Dynamic Programming
- DP[i][j] = ความยาว snake สูงสุดที่จบที่ (i,j)
- DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + 1 ถ้าตัวเลขต่างกัน 1
- ติดตามตำแหน่งที่มีค่าสูงสุด แล้ว trace back สร้าง path
ตัวอย่างโค้ด
M = 4
N = 4
def get_path(grid, mat, i, j):
path = []
pt = [i, j]
path.append(pt)
while mat[i][j] != 0:
if i > 0 and grid[i][j] - 1 == grid[i-1][j]:
pt = [i-1, j]
path.append(pt)
i -= 1
elif j > 0 and grid[i][j] - 1 == grid[i][j-1]:
pt = [i, j-1]
path.append(pt)
j -= 1
return path
def get_sequence(grid):
lookup = [[0]*N for _ in range(M)]
max_len = 0
max_row = max_col = 0
for i in range(M):
for j in range(N):
if i or j:
if i > 0 and abs(grid[i-1][j] - grid[i][j]) == 1:
lookup[i][j] = max(lookup[i][j], lookup[i-1][j] + 1)
if max_len < lookup[i][j]:
max_len = lookup[i][j]
max_row, max_col = i, j
if j > 0 and abs(grid[i][j-1] - grid[i][j]) == 1:
lookup[i][j] = max(lookup[i][j], lookup[i][j-1] + 1)
if max_len < lookup[i][j]:
max_len = lookup[i][j]
max_row, max_col = i, j
print("Maximum length:", max_len)
path = get_path(lookup, grid, max_row, max_col)
print("Sequence is:")
for ele in reversed(path):
print(f"{grid[ele[0]][ele[1]]} [{ele[0]}, {ele[1]}]")
grid = [
[10, 7, 6, 3],
[9, 8, 7, 6],
[8, 4, 2, 7],
[2, 2, 2, 8]
]
get_sequence(grid)
ผลลัพธ์
Maximum length: 6 Sequence is: 10 [0, 0] 9 [1, 0] 8 [1, 1] 7 [1, 2] 6 [1, 3] 7 [2, 3] 8 [3, 3]
สรุป: DP บนกริด O(M×N) time และ space สร้างตารางความยาวสูงสุด แล้ว trace back ได้ path
