Unique Paths
Một robot bắt đầu ở ô trên cùng bên trái của một lưới có m hàng và n cột, rồi phải đến ô dưới cùng bên phải. Mỗi bước di chuyển đưa robot sang phải một ô hoặc xuống dưới một ô. Hãy trả về số đường đi khác nhau mà robot có thể đi.
Hàm
- minteger
- số hàng trong lưới
- ninteger
- số cột trong lưới
- Trả vềinteger
- số đường đi khác nhau từ ô trên cùng bên trái đến ô dưới cùng bên phải
Ràng buộc
1 ≤ m, n ≤ 100- Đáp án nhiều nhất là
2 × 109, nên vừa với số nguyên có dấu 32 bit.
Ví dụ
- Đầu vào
- m = 3n = 4
- Đầu ra
- 10
- Giải thích
- Mỗi đường đi gồm 2 bước xuống và 3 bước sang phải, tổng cộng 5 bước. Đường đi được xác định bởi 2 trong số 5 bước đi xuống, và có 10 cách chọn chúng.
- Đầu vào
- m = 1n = 6
- Đầu ra
- 1
- Giải thích
- Với một hàng duy nhất, robot chỉ có thể di chuyển sang phải 5 lần, nên chỉ có đúng một đường đi.
- Đầu vào
- m = 4n = 5
- Đầu ra
- 35
- Giải thích
- Mỗi đường đi có 3 bước xuống và 4 bước sang phải. Chọn 3 trong 7 bước để đi xuống, ta có 7 × 6 × 5 / 6 = 35 đường đi.
Câu hỏi mở rộng
Với một lưới 100 × 100, đáp án có 59 chữ số. Bạn sẽ dùng công thức nào để trả về kết quả theo modulo 10^9+7, khi không còn chia cho i được nữa?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Ngay trước khi bước vào một ô, robot có thể đã ở đâu?
Các đường đi vào một ô là các đường đi vào ô phía trên cộng với các đường đi vào ô bên trái. Hàng trên cùng và cột ngoài cùng bên trái mỗi phần có đúng một đường đi.
Điền số lượng theo từng hàng, từ trái sang phải, giữ các số trên một hàng duy nhất. Hoặc đếm trực tiếp các thứ tự di chuyển: một đường đi tương ứng với việc chọn
m-1trong sốm+n-2bước di chuyển để đi xuống.
Lời giải
Liệt kê các đường đi là bất khả thi: một lưới 17 × 17 có 601,080,390 đường đi. Thay vào đó, hãy đếm. Số đường đi đến một ô bằng tổng số đường đi đến ô phía trên và ô bên trái, nhờ đó ta có thể điền bảng chỉ trong một lượt. Mỗi đường đi chỉ là một thứ tự gồm các bước xuống và sang phải, từ đó ta có công thức dạng đóng.
Đếm mọi đường đi bằng đệ quy
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Nước đi cuối cùng của robot là đi xuống từ ô phía trên hoặc đi sang phải từ ô bên trái. Vì vậy, uniquePaths(m, n) = uniquePaths(m-1, n) + uniquePaths(m, n-1), và lưới có một hàng hoặc một cột có đúng 1 đường đi. Mỗi đường đi kết thúc bằng đúng một trong hai nước đi này, nên mỗi đường đi chỉ được đếm một lần.
Mỗi đường đi đều kết thúc ở một trường hợp cơ sở trả về 1, nên số lần gọi ít nhất bằng đáp án: lưới 17 × 17 cần hơn 600 triệu lần gọi. Cùng một lưới nhỏ được tính đi tính lại.
Thuật toán
- Nếu
mhoặcnbằng 1, hãy trả về 1: chỉ có một đường đi thẳng. - Nếu không, hãy đếm các đường đi có bước cuối cùng đi xuống,
uniquePaths(m-1, n). - Đếm các đường đi có bước cuối cùng đi sang phải,
uniquePaths(m, n-1). - Trả về tổng của chúng.
def uniquePaths(m, n):
# One row or one column: the only path is a straight line
if m == 1 or n == 1:
return 1
# The last move came down from the row above or right from the column before
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)Điền vào lưới từng hàng một
Ý tưởng
Đệ quy liên tục hỏi về cùng một nhóm ô m × n. Đếm mỗi ô một lần, theo thứ tự sao cho các giá trị đầu vào của ô đã sẵn sàng.
Trạng thái: paths[r][c] là số đường đi từ ô trên cùng bên trái đến hàng r, cột c. Công thức truy hồi: paths[r][c] = paths[r-1][c] + paths[r][c-1], gồm các đường đi đến từ phía trên cộng với các đường đi đến từ bên trái. Trường hợp cơ sở: mỗi ô ở hàng trên cùng và cột bên trái có 1 đường đi. Thứ tự: lần lượt từng hàng, từ trái sang phải. Với m = 3, n = 4, các hàng là 1 1 1 1, 1 2 3 4, 1 3 6 10, và đáp án là 10.
Quá trình điền chỉ đọc hàng phía trên, nên chỉ cần giữ lại một hàng. Trước khi cập nhật row[c], nó vẫn chứa số lượng từ phía trên, còn row[c-1] đã chứa số lượng mới ở bên trái, nên row[c] += row[c-1] là toàn bộ công thức truy hồi với bộ nhớ O(n).
Thuật toán
- Tạo
rowgồmnphần tử, tất cả đều bằng 1: đây là hàng trên cùng. - Lặp lại
m-1lần, mỗi lần cho một hàng bên dưới hàng trên cùng. - Trong mỗi hàng, với
ctừ 1 đếnn-1, cộngrow[c-1]vàorow[c].row[0]vẫn bằng 1: đây là cột bên trái. - Trả về
row[n-1].
def uniquePaths(m, n):
# row[c] counts the paths into column c of the current row.
# The top row is all 1s: the only way along it is straight right.
row = [1] * n
for _ in range(m - 1):
for c in range(1, n):
# Paths from above (the old row[c]) plus paths from the left (the new row[c-1])
row[c] += row[c - 1]
return row[n - 1]Đếm số nước đi bằng hệ số nhị thức
Ý tưởng
Mọi đường đi đều có m-1 bước đi xuống và n-1 bước đi sang phải, tổng cộng m+n-2 bước theo một thứ tự nào đó. Mọi cách sắp xếp đều tạo thành một đường đi hợp lệ: đường đi không bao giờ có nhiều hơn m-1 bước xuống hoặc n-1 bước sang phải, nên không bao giờ đi ra khỏi lưới. Vì vậy, một đường đi tương ứng với việc chọn m-1 bước đi xuống, và đáp án là C(m+n-2, m-1).
Hãy tính hệ số mà không dùng giai thừa. Với N = m+n-2 và k = min(m, n)-1, nhân với N-k+i rồi chia cho i, với i chạy từ 1 đến k. Sau bước i, giá trị là C(N-k+i, i), một số nguyên, nên mọi phép chia đều chính xác. Với m = 3, n = 4: 1 × 4 / 1 = 4, rồi 4 × 5 / 2 = 10. Chọn theo cạnh ngắn hơn giúp vòng lặp có không quá 99 lần lặp.
Thuật toán
- Đặt
N = m+n-2là số bước di chuyển vàk = min(m, n)-1. - Khởi tạo biến đếm 64 bit bằng 1.
- Với
ichạy từ 1 đếnk, nhân biến đếm vớiN-k+i, sau đó chia choi. - Trả về biến đếm.
def uniquePaths(m, n):
# A path is m+n-2 moves; count the ways to choose which of them go down.
# Choose along the shorter side so the loop stays short.
moves = m + n - 2
k = min(m, n) - 1
count = 1
for i in range(1, k + 1):
# count goes from C(moves-k+i-1, i-1) to C(moves-k+i, i); the division is exact
count = count * (moves - k + i) // i
return count
Lỗi thường gặp và trường hợp biên
- Tính
(m+n-2)!rồi chia cho hai giai thừa còn lại. 21! đã vượt phạm vi 64 bit, vàm+n-2đạt 105 trong lưới 100 × 7. - Chia trước khi nhân, như trong
count / i * (N-k+i).countkhông phải lúc nào cũng chia hết choi, nên phép chia sẽ làm tròn xuống. - Giữ tích đang tính trong phạm vi 32 bit. Trước phép chia cuối cùng, tích bằng
knhân với đáp án: 16 × 601,080,390, khoảng 9.6 × 10^9, với lưới 17 × 17. - Bắt đầu hàng trên cùng hoặc cột bên trái ở 0 thay vì 1. Mọi ô đều trở thành 0, dù lưới có một hàng hoặc một cột thì chỉ có đúng 1 đường đi.
Câu hỏi thường gặp3
Độ phức tạp thời gian của Unique Paths là bao nhiêu?
Bảng quy hoạch động cần thời gian O(m × n) và bộ nhớ O(n) khi bạn chỉ giữ lại một hàng. Công thức nhị thức cần thời gian O(min(m, n)) và bộ nhớ O(1). Đệ quy thuần túy thực hiện ít nhất số lần gọi bằng số đường đi, tức là tăng theo hàm mũ theo m + n.
Làm thế nào để giải bài toán Đường đi duy nhất khi một số ô bị chặn?
Dùng cùng một bảng và đặt số đường đi đến ô bị chặn thành 0 để không có đường nào đi qua ô đó. Hàng trên cùng và cột bên trái không còn toàn số 1 nữa: mọi ô nằm sau một ô bị chặn trong hàng trên cùng đều có 0 đường đi. Công thức không còn dùng được vì giả định rằng mọi thứ tự di chuyển đều được phép.
Tại sao bảng Unique Paths khớp với tam giác Pascal?
Mỗi ô cộng giá trị của ô phía trên và ô bên trái, đây là quy tắc tạo nên tam giác Pascal khi đọc theo các đường chéo. Ô ở hàng r và cột c chứa C(r+c, r), vì vậy ô dưới cùng bên phải chứa C(m+n-2, m-1), theo công thức nhị thức.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def uniquePaths(m, n):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
m = 3 n = 4
Đầu ra mong đợi
10