Tìm đường trên lưới bằng quy hoạch động

Lan cần đưa robot qua kho hàng gồm 3 hàng và 4 cột. Robot xuất phát ở góc trên trái, chỉ đi sang phải hoặc xuống dưới, và không đi vào ô có thùng hàng. Lan muốn biết có bao nhiêu đường tới góc dưới phải. Nếu thử từng đường, số lựa chọn tăng rất nhanh khi kho lớn. Ta có thể tận dụng kết quả đã tính cho từng ô.

Mỗi đường tới một ô có bước cuối từ trên hoặc trái

Đánh số hàng từ 0 đến n - 1, cột từ 0 đến m - 1. Robot chỉ đi xuống hoặc sang phải. Vì thế, trước khi tới ô (i, j), robot phải ở ô (i - 1, j) hoặc (i, j - 1), nếu ô đó tồn tại.

Gọi dp[i][j] là số đường hợp lệ từ góc trên trái tới ô (i, j). Đây là trạng thái (state): nó cho biết ta đang lưu câu trả lời cho bài toán con nào. Hai nhóm đường có bước cuối khác nhau, nên cộng số đường ở hai nguồn không đếm trùng.

Ô xuất phát trống có đúng một cách: đứng tại chỗ, không thực hiện bước nào. Nếu xuất phát bị chặn thì không có đường nào. Ở hàng đầu không có nguồn phía trên; ở cột đầu không có nguồn bên trái. Không dùng chỉ số âm để giả làm ô ngoài lưới, vì Python xem -1 là phần tử cuối.

Lưới sau có một vật cản ở giữa. Bảng được chính chương trình tính; dấu # trong dữ liệu là ô bị chặn.

Ô bị chặn nhận 0, nên không truyền đường đi qua nó. Ô ngay bên phải vật cản chỉ nhận đường từ phía trên. Ô dưới vật cản chỉ nhận đường từ bên trái. Tại mỗi ô còn lại, hai nguồn đại diện cho hai loại bước cuối khác nhau.

Điền từ trên xuống và từ trái sang phải

Thứ tự này bảo đảm ô trên đã thuộc một hàng hoàn chỉnh, còn ô trái đã được tính trong hàng hiện tại. Chuyển trạng thái (transition) là quy tắc tính kết quả tại một ô từ những kết quả trước đó. Với ô trống không phải điểm xuất phát, quy tắc là dp[i][j] = trên + trái.

Chương trình sau đọc kích thước và từng hàng của lưới. Ký tự . là ô trống, # là vật cản. Nó in số đường theo modulo 1_000_000_007, tức phần dư khi chia cho số đó.

3 4
....
.#..
....

MOD = 1_000_000_007
n, m = map(int, input().split())
grid = [input().strip() for _ in range(n)]
dp = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if grid[i][j] == "#":
            continue
        if i == 0 and j == 0:
            dp[i][j] = 1
            continue
        top = dp[i - 1][j] if i > 0 else 0
        left = dp[i][j - 1] if j > 0 else 0
        dp[i][j] = (top + left) % MOD
print(dp[-1][-1])

4

Với dữ liệu này, bốn đường đi tới đích tránh được vật cản. Nếu đổi ô cuối thành #, kết quả là 0. Nếu lưới chỉ có một ô trống, kết quả là 1; nếu ô duy nhất bị chặn, kết quả là 0.

Tính đúng đắn dựa trên thứ tự điền. Ban đầu, giá trị tại điểm xuất phát đúng theo định nghĩa. Giả sử hai nguồn đã đúng, mọi đường tới ô hiện tại thuộc đúng một nhóm theo bước cuối. Cộng hai nhóm được đủ tất cả đường, còn ô chặn không có đường nào. Lặp lập luận này tới đích cho kết quả đúng.

Mỗi ô xét nhiều nhất hai nguồn. Thời gian là O(nm), bộ nhớ bảng là O(nm). Ví dụ lưới 1000 × 1000 có một triệu ô, tức khoảng một triệu lần cập nhật. Một phép chia lấy dư sau mỗi lần cộng giữ giá trị nhỏ; tính chất cộng theo modulo bảo toàn phần dư cuối cùng.

Nếu robot phải đi qua một trạm cố định, mỗi đường được tách duy nhất thành đoạn từ đầu tới trạm và đoạn từ trạm tới đích. Theo quy tắc nhân đã học ở Bài 9, mỗi cách chọn đoạn đầu ghép được với mọi cách chọn đoạn sau. Tích hai số cách chính là số đường qua trạm. Nếu trạm bị chặn hoặc một đoạn không có đường, tích bằng 0.

Ví dụ sau tính riêng hai đoạn của lưới 3 × 4, với trạm ở hàng 2, cột 2. Các tọa độ này được đếm từ 1; mọi ô đều trống.

from math import comb
first = comb(2, 1)
second = comb(3, 1)
print(first, second, first * second)

2 3 6

Có hai đường tới trạm và ba đường từ trạm tới đích, nên có sáu đường qua trạm. Với vật cản, tính hai số bằng quy hoạch động trên từng hình chữ nhật tương ứng. Hai lượt xét tổng cộng không quá hai lần số ô của lưới, nên thời gian vẫn là O(nm); một hàng trạng thái dùng O(m) bộ nhớ.

Hàng đầu và cột đầu cho thấy tác dụng của vật cản

Trên một hàng, robot không thể đi vòng qua vật cản. Sau một ô bị chặn, những ô còn lại trên hàng đó đều không tới được từ điểm đầu. Cột đầu có lập luận tương tự.

row = "..#..."
ways = 1
for cell in row:
    if cell == "#":
        ways = 0
    print(ways, end=" ")
print()

1 1 0 0 0 0 

Số cách bằng 0 sau vật cản, dù các ô phía sau vẫn trống. Điều này khác với việc khởi tạo cả hàng đầu bằng 1 mà không kiểm tra dữ liệu. Trường hợp một cột được xử lý bằng cùng quy tắc nguồn hợp lệ.

def count(grid):
    n, m = len(grid), len(grid[0])
    dp = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == "#":
                continue
            if i == j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = (dp[i-1][j] if i else 0) + (dp[i][j-1] if j else 0)
    return dp[-1][-1]
for grid in [["."], ["#"], ["#.", ".."], ["..", ".#"]]:
    print(count(grid))

1
0
0
0

Hai trường hợp cuối có điểm đầu hoặc đích bị chặn. Dù các ô khác trống, không có đường hợp lệ đi từ đầu tới cuối.

Công thức tổ hợp nhanh khi không có vật cản

Xem Bài 9 về tổ hợp. Trong lưới n × m không có vật cản, mỗi đường gồm đúng n - 1 bước xuống và m - 1 bước phải. Chọn vị trí của các bước xuống trong tổng n + m - 2 bước cho C(n + m - 2, n - 1) đường.

from math import comb
n, m = 3, 4
dp = [[0] * m for _ in range(n)]
dp[0][0] = 1
for i in range(n):
    for j in range(m):
        if i or j:
            dp[i][j] = (dp[i-1][j] if i else 0) + (dp[i][j-1] if j else 0)
print(comb(n + m - 2, n - 1))
print(dp[-1][-1])

10
10

Hai kết quả trùng nhau vì cả hai đếm cùng tập đường. Công thức này không tự loại đường đi qua vật cản. Khi vật cản nằm ở nhiều vị trí tùy ý, bảng quy hoạch động giữ thông tin từng ô và loại các đường không hợp lệ ngay khi tính.

Chi phí nhỏ nhất dùng phép chọn nhỏ nhất thay cho phép cộng số cách

Giả sử mỗi ô có một số nguyên là chi phí đi vào ô đó, kể cả ô xuất phát. Đặt best[i][j] là tổng chi phí nhỏ nhất trong các đường tới (i, j). Với ô đầu, best[0][0] bằng chi phí của chính nó. Với ô khác, lấy giá trị nhỏ hơn trong hai nguồn hợp lệ rồi cộng chi phí ô hiện tại.

Bảng dưới cho thấy cả chi phí đầu vào và kết quả sau khi tính. Chi phí âm vẫn dùng được vì mỗi bước tăng hàng hoặc cột, nên không thể quay vòng để giảm tổng mãi.

Đường tới ô giữa có thể qua trên hoặc trái. Với mỗi nguồn, nối thêm cùng một ô hiện tại sẽ cộng cùng chi phí. Do đó đường tốt nhất tới ô hiện tại phải nối từ đường tốt nhất trong hai nguồn. Lập luận đúng theo thứ tự điền, kể cả khi có số âm.

3 3
3 1 8
2 -4 2
7 1 3

n, m = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(n)]
best = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if i == 0 and j == 0:
            best[i][j] = cost[i][j]
            continue
        sources = []
        if i > 0:
            sources.append(best[i - 1][j])
        if j > 0:
            sources.append(best[i][j - 1])
        best[i][j] = min(sources) + cost[i][j]
print(best[-1][-1])

4

Ở đây tổng nhỏ nhất là 4, tính cả chi phí ô đầu và ô cuối. Bài toán vẫn có nm ô và tối đa hai nguồn mỗi ô, nên thời gian và bộ nhớ lần lượt là O(nm) và O(nm).

Nếu đề còn hỏi có bao nhiêu đường đạt chi phí nhỏ nhất, một con số chi phí chưa đủ. Ta lưu thêm ways[i][j], số đường đạt đúng chi phí tốt nhất tại ô đó. Điểm đầu có một đường nếu không bị chặn. Tại mỗi ô khác, xét các nguồn tới được và tìm chi phí nguồn nhỏ nhất. Chỉ cộng ways của nguồn có chi phí bằng giá trị nhỏ nhất này.

Chẳng hạn, hai nguồn có chi phí lần lượt là 5 và 5, với 2 và 3 đường tốt nhất. Sau khi thêm cùng chi phí ô hiện tại, cả hai nguồn vẫn bằng nhau, nên có 2 + 3 = 5 đường tốt nhất. Nếu chi phí hai nguồn là 5 và 7, chỉ lấy hai đường của nguồn thứ nhất. Cộng cả hai sẽ tính cả các đường không tối ưu.

sources = [(5, 2), (5, 3)]
cell_cost = -1
best_source = min(cost for cost, ways in sources)
best_cost = best_source + cell_cost
best_ways = sum(ways for cost, ways in sources if cost == best_source)
print(best_cost, best_ways)

4 5

Quy tắc này vẫn dựa trên bước cuối: đường qua nguồn trên và đường qua nguồn trái là hai nhóm khác nhau. Các nguồn kém hơn không thể trở nên tốt hơn sau khi cùng cộng chi phí ô hiện tại. Vì vậy số đường tối ưu được cộng đúng và đủ. Khi cần phần dư, chỉ lấy modulo cho số đường; chi phí phải giữ nguyên để so sánh.

Nếu có ô chặn, cần phân biệt ô chưa tới được với ô có tổng bằng 0. Có thể dùng None để đánh dấu không tới được, chỉ cộng chi phí với nguồn khác None. Đừng cộng một giá trị vô cực giả với số âm rồi kết luận đã có đường.

grid = [[0, None, 5], [2, None, 1]]
n, m = len(grid), len(grid[0])
best = [[None] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if grid[i][j] is None:
            continue
        if i == j == 0:
            best[i][j] = grid[i][j]
            continue
        sources = []
        if i and best[i-1][j] is not None:
            sources.append(best[i-1][j])
        if j and best[i][j-1] is not None:
            sources.append(best[i][j-1])
        if sources:
            best[i][j] = min(sources) + grid[i][j]
print(best[0][0], best[-1][-1])

0 None

Điểm đầu có chi phí 0, nhưng đích không thể tới vì cả cột giữa bị chặn. Giá trị None biểu thị điều đó, không phải một chi phí.

Một hàng nhớ kết quả từ trên và trái

Khi chỉ cần số đường tới đích, không cần giữ tất cả hàng cũ. Trước khi cập nhật cột j, dp[j] giữ số đường từ ô phía trên. Sau khi cập nhật cột j - 1, dp[j - 1] giữ số đường từ ô bên trái của hàng hiện tại.

Hình minh họa lúc xử lý hàng thứ hai của lưới trước đó. Cột 1 bị chặn nên thành 0. Cột 2 cộng 1 từ phía trên với 0 bên trái, vẫn bằng 1. Cột 3 cộng 1 từ phía trên với 1 bên trái, thành 2. Cần xóa dp[j] tại vật cản, nếu không giá trị hàng trước sẽ đi xuyên qua tường.

MOD = 1_000_000_007
grid = ["....", ".#..", "...."]
m = len(grid[0])
dp = [0] * m
dp[0] = 1
for row in grid:
    for j in range(m):
        if row[j] == "#":
            dp[j] = 0
        elif j > 0:
            dp[j] = (dp[j] + dp[j - 1]) % MOD
    print(*dp)
print("Đích:", dp[-1])

1 1 1 1
1 0 1 2
1 1 2 4
Đích: 4

Trước vòng lặp, dp[0] = 1 tạo nguồn cho điểm đầu. Nếu điểm đầu bị chặn, nhánh đầu tiên xóa nguồn đó. Thứ tự trái sang phải rất quan trọng: đảo chiều sẽ lấy giá trị bên trái của hàng cũ, không phải hàng hiện tại.

left_to_right = [1, 1, 1]
right_to_left = left_to_right[:]
for j in range(1, 3):
    left_to_right[j] += left_to_right[j - 1]
for j in range(2, 0, -1):
    right_to_left[j] += right_to_left[j - 1]
print(left_to_right)
print(right_to_left)

[1, 2, 3]
[1, 2, 2]

Hai danh sách bắt đầu từ hàng trước [1, 1, 1]. Chỉ danh sách đầu dùng đúng giá trị mới ở bên trái khi tính cột cuối. Cách một hàng vẫn tốn O(nm) thời gian nhưng chỉ cần O(m) bộ nhớ cho bảng. Nếu cần khôi phục toàn bộ đường, phải lưu thêm thông tin lựa chọn hoặc tính lại thích hợp.

Con số O(m) chỉ tính bộ nhớ cho trạng thái. Nếu chương trình giữ toàn bộ dữ liệu đầu vào, lưới vẫn chiếm O(nm) bộ nhớ. Đọc và xử lý lần lượt từng hàng giúp tránh khoản lưu trữ đó khi đề cho phép.

Hướng đi quyết định thứ tự và giới hạn áp dụng

Mỗi bước xuống hoặc phải làm i + j tăng một. Do đó không có chu trình, và các nguồn của một ô đều xuất hiện trước nó. Nếu thêm bước lên hoặc trái, điều này không còn đúng: một ô có thể phụ thuộc vào ô chưa tính hoặc quay lại ô cũ.

reachable = [False, False, True]
for j in range(3):
    if j > 0 and reachable[j - 1]:
        reachable[j] = True
    if j + 1 < 3 and reachable[j + 1]:
        reachable[j] = True
print(reachable)

[False, True, True]

Ở ví dụ này được phép đi hai chiều và bắt đầu tại ô cuối. Ô giữa trở thành có thể tới, nhưng ô đầu đã bị duyệt trước đó. Kết quả một lượt quét vì vậy chưa đầy đủ. Cần chọn thuật toán phù hợp với luật di chuyển, chẳng hạn tìm đường trên đồ thị khi được đi bốn hướng.

Lỗi thường gặp

Tóm tắt

• Định nghĩa trạng thái theo đúng đại lượng cần đếm hoặc tối ưu.
• Với bước xuống/phải, mọi đường tới ô trống đi từ trên hoặc trái.
• Tính từ trên xuống, trái sang phải; xử lý riêng điểm đầu, biên và vật cản.
• Một hàng đủ cho kết quả cuối khi chỉ phụ thuộc ô trên và trái.
• Kiểm tra hướng đi trước khi dùng thứ tự tính này.

Kiểm tra nhanh

Đọc thêm

• AtCoder Educational DP Contest: Grid 1: bài đếm đường có vật cản.
• Python: cấu trúc dữ liệu: danh sách và danh sách lồng nhau.