Climbing Stairs
Bạn đứng dưới chân một cầu thang có n bậc. Mỗi lần di chuyển, bạn có thể bước lên 1 hoặc 2 bậc. Hai cách đi được tính là khác nhau nếu chuỗi bước đi khác nhau, vì vậy 1, 2 và 2, 1 là hai cách. Hàm của bạn nhận n và trả về số cách khác nhau để lên đến đỉnh.
Hàm
- ninteger
- số bậc cầu thang
- Trả vềinteger
- số chuỗi khác nhau gồm các bước 1 và bước 2 để đến bậc n
Ràng buộc
1 ≤ n ≤ 45- Đáp án nằm trong phạm vi số nguyên có dấu 32 bit:
n = 45cho kết quả1836311903.
Ví dụ
- Đầu vào
- n = 3
- Đầu ra
- 3
- Giải thích
- Có thể leo ba bậc theo cách
1, 1, 1, theo cách1, 2hoặc theo cách2, 1, vậy có 3 cách.
- Đầu vào
- n = 5
- Đầu ra
- 8
- Giải thích
- Mọi cách leo lên bậc 5 đều kết thúc bằng bước đi 1 bậc từ bậc 4 (có 5 cách để đến đó) hoặc bước đi 2 bậc từ bậc 3 (có 3 cách), vậy đáp án là
5 + 3 = 8.
Câu hỏi mở rộng
Nếu một số bậc bị hỏng và bạn không thể bước lên chúng thì sao? Công thức truy hồi thay đổi như thế nào, và số cách đi cho một bậc bị hỏng là bao nhiêu?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Hãy xem bước cuối cùng của bất kỳ lượt leo nào đến bậc
n. Ngay trước bước đó, bạn có thể đã đứng ở đâu?Mỗi lần leo đến bậc
nđều kết thúc bằng một bước từ bậcn-1hoặc hai bước từ bậcn-2, không bao giờ là cả hai. Vì vậy, số cách đến bậcnbằng số cách đến bậcn-1cộng với số cách đến bậcn-2.Bắt đầu với số cách đi 1 bước (1 cách) và 2 bước (2 cách), rồi tính dần lên. Bạn chỉ cần giữ lại hai số đếm gần nhất, mỗi số đếm mới là tổng của hai số đó.
Lời giải
Liệt kê mọi cách leo sẽ thất bại: 45 bậc có đến 1836311903 cách. Trước bước cuối cùng, mỗi cách leo đến bậc n đều đứng ở bậc n-1 hoặc bậc n-2, vì vậy ways(n) = ways(n-1) + ways(n-2), theo quy luật truy hồi Fibonacci. Hãy xây dựng kết quả từ dưới lên, bạn chỉ cần hai biến (variable).
Đệ quy đơn giản ở bước cuối cùng
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Chia các cách leo đến bậc n theo bước cuối cùng. Cách leo kết thúc bằng bước 1 đã đứng ở bậc n-1, cách leo kết thúc bằng bước 2 đã đứng ở bậc n-2, và không cách leo nào kết thúc theo cả hai cách, nên cộng hai số lượng này lại. Một bậc có một cách leo và hai bậc có hai cách leo, nên trả về n khi n ≤ 2.
Đệ quy quên những gì nó đã tính. climbStairs(5) yêu cầu tính bậc 3 hai lần và bậc 2 ba lần, tổng cộng 9 lần gọi, còn n = 45 cần 2269806339 lần gọi.
Thuật toán
- Nếu
n ≤ 2, trả vền. - Đếm số cách leo đến bậc
n-1bằng một lời gọi đệ quy. - Đếm số cách leo đến bậc
n-2bằng lời gọi đệ quy thứ hai. - Trả về tổng của hai số đếm.
def climbStairs(n):
if n <= 2:
return n # 1 step: one way, 2 steps: two ways
return climbStairs(n - 1) + climbStairs(n - 2)Đệ quy có ghi nhớ
Ý tưởng
Số cách ở bước k chỉ phụ thuộc vào k, nên một khi đã biết thì sẽ không thay đổi. Lần đầu tính, hãy ghi số đó vào một ô nhớ đệm; những lần yêu cầu sau sẽ đọc từ ô đó thay vì gọi đệ quy. Như vậy, mỗi số cách từ bước 3 đến bước n chỉ được tính một lần, với một phép cộng: thời gian O(n). Với n = 5, lần yêu cầu thứ hai cho bước 3 sẽ tra cứu giá trị.
Số 0 trong một ô nghĩa là chưa biết, điều này an toàn vì mọi số cách thực tế đều ít nhất là 1.
Thuật toán
- Tạo một bộ nhớ đệm có
n + 1ô, tất cả đều bằng 0. - Trong hàm trợ giúp đệ quy, trả về
kkhik ≤ 2. - Nếu ô bộ nhớ đệm cho
kbằng 0, hãy điền vào đó tổng kết quả của hàm trợ giúp vớik-1vàk-2. - Trả về ô bộ nhớ đệm.
- Gọi hàm trợ giúp với
n.
def climbStairs(n):
memo = [0] * (n + 1) # memo[k] = ways to reach step k, 0 = not known yet
def ways(k):
if k <= 2:
return k
if memo[k] == 0:
memo[k] = ways(k - 1) + ways(k - 2)
return memo[k]
return ways(n)Từ dưới lên với hai biến
Ý tưởng
Thay vào đó, hãy tính từ dưới lên. Khi tính số lượng cho bước k, bạn chỉ đọc số lượng ở k-1 và k-2, không cần dùng lại các số lượng cũ hơn. Vì vậy, hai biến có thể thay thế bảng ghi nhớ.
Với n = 5, cặp (prev, curr) lần lượt chuyển từ (1, 2) sang (2, 3), (3, 5) rồi (5, 8), và curr = 8 là đáp án. Hãy tính next trước khi ghi đè lên prev, nếu không tổng sẽ dùng sai giá trị.
Thuật toán
- Nếu
n ≤ 2, trả vền. - Đặt
prev = 1vàcurr = 2. - Với
ktừ 3 đếnn, tínhnext = prev + curr, sau đó đặtprev = currvàcurr = next. - Trả về
curr.
def climbStairs(n):
if n <= 2:
return n
prev, curr = 1, 2 # ways to reach steps 1 and 2
for _ in range(n - 2):
prev, curr = curr, prev + curr
return curr
Lỗi thường gặp và trường hợp biên
- Các trường hợp cơ sở không đúng. Hai bước có hai cách leo:
1, 1và2. Trả về 1 khin = 2làm lệch mọi đáp án sau đó: bạn nhận được 2 khin = 3thay vì 3. - Đếm số lựa chọn thay vì số trình tự. Chỉ đếm số lần bạn đi 2 bước sẽ cho kết quả
n/2 + 1, tức là 3 khin = 5thay vì 8. - Điền bảng mà không kiểm tra điều kiện. Với
n = 1, bảng cón + 1 = 2ô không đủ chỗ cho bước 2. Hãy trả vềntrước khin ≤ 2. - Chạy quá một bước. Số cách cho 46 bước là 2971215073, giá trị này vượt quá giới hạn của
int32 bit và trở thành số âm trong Java, C hoặc C#.
Câu hỏi thường gặp3
Vì sao bài toán leo cầu thang lại là một bài toán Fibonacci?
Mỗi cách leo lên bậc n kết thúc bằng một bước từ n-1 hoặc hai bước từ n-2, theo quy tắc Fibonacci. Với ways(1) = 1 và ways(2) = 2, số cách lần lượt là 1, 2, 3, 5, 8, 13: dãy Fibonacci dịch sang phải một vị trí, ways(n) = F(n+1).
Độ phức tạp thời gian của bài toán leo cầu thang là gì?
Vòng lặp từ dưới lên thực hiện n-2 phép cộng: độ phức tạp thời gian O(n) và dùng thêm O(1) không gian. Đệ quy có bộ nhớ đệm có độ phức tạp thời gian O(n) và dùng O(n) không gian. Đệ quy thông thường có độ phức tạp thời gian hàm mũ, với số lần gọi tăng khoảng 1.618 lần sau mỗi bước.
Làm thế nào để giải bài toán leo cầu thang với mỗi bước dài 1, 2 hoặc 3 bậc?
Hãy tiếp tục chia các cách leo theo bước cuối cùng: ways(n) = ways(n-1) + ways(n-2) + ways(n-3). Bắt đầu với ways(0) = 1 (cách leo rỗng), ways(1) = 1 và ways(2) = 2, rồi giữ lại ba số đếm gần nhất thay vì hai. Độ phức tạp thời gian vẫn là O(n) và độ phức tạp không gian là O(1).
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 climbStairs(n):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Đối số
n = 3
Đầu ra mong đợi
3