Cầu Thang Nhà A Phủ (DPSTEPS)

Nguồn: LuyenCode Độ khó: Dễ Quy hoạch động QHĐ tuyến tính Fibonacci

Đề bài

DPSTEPS – Cầu thang nhà A Phủ

Hôm nay Bờm đến thăm nhà A Phủ, A Phủ ở nhà sàn, để lên nhà A Phủ phải đi bằng cầu thang. Cầu thang nhà A Phủ có $N$ bậc, trong đó có $K$ bậc đã bị mục nên không thể bước lên được (nhà A Phủ rất nghèo, từ ngày cấm trồng cây anh túc thì nhà A Phủ sống rất khó khăn). Chú ý: Bậc thứ $N$ là sàn nhà A Phủ, bậc này không bị hỏng. Do đi đường mệt nên Bờm chỉ còn sức để có thể bước mỗi lần một hoặc tối đa hai bậc thang mà thôi. Vừa định bước lên cầu thang thì Bờm chợt nảy ra một câu hỏi: Có bao nhiêu cách bước từ sân lên nhà A Phủ? Các em hãy tính giúp Bờm nhé.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương $N$ và $K$ cách nhau bởi một dấu cách;
• Dòng thứ hai chứa $K$ số nguyên dương $b_1, b_2, \ldots, b_K$ là chỉ số các bậc thang bị hỏng, mỗi số cách nhau bởi một dấu cách.

Giới hạn: $1 \le N \le 10^5;\ 0 \le K \le N;\ 1 \le b_i \lt N$.

Dữ liệu ra: Một số nguyên duy nhất là số cách bước lên nhà A Phủ (do số cách có thể rất lớn nên ta chỉ lấy phần dư khi chia cho 1000000007).

Input #1

5 1
2

Output #1

2

Gợi ý (của đề): Bờm có thể bước như sau: $1 \to 3 \to 4 \to 5$ hoặc $1 \to 3 \to 5$, do đó có $2$ cách.

Hình trong đề: cầu thang 5 bậc, bậc 2 bị hỏng (tô xám, viền đỏ), bậc 5 là sàn nhà A Phủ.

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Đây là "người anh em" của bài leo cầu thang kinh điển (dãy Fibonacci), chỉ thêm chút gia vị là có vài bậc bị mục không đặt chân lên được.

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Bờm đứng ở sân (ta coi sân là bậc $0$), cần lên sàn nhà là bậc $N = 5$. Mỗi lần Bờm bước lên $1$ hoặc $2$ bậc, và không được đặt chân lên bậc hỏng là bậc $2$. Ta liệt kê:

• Từ sân, Bờm chỉ có thể lên bậc $1$ hoặc bậc $2$. Bậc $2$ hỏng nên bắt buộc lên bậc $1$.
• Từ bậc $1$, bước $1$ thì đạp vào bậc $2$ (hỏng) → không được; nên phải bước $2$ lên bậc $3$.
• Từ bậc $3$: hoặc bước $1$ lên bậc $4$ rồi bước $1$ lên bậc $5$, hoặc bước $2$ lên thẳng bậc $5$.

Sân→1→3→4→5

Sân→1→3→5

Vậy có đúng 2 cách, khớp với output. (Đề viết $1 \to 3 \to 4 \to 5$ là bỏ qua cái "sân" ở đầu thôi nha.)

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Đệ quy thử mọi cách bước · O(2^N) · chỉ để hiểuCách 2Quy hoạch động 4 bước · O(N) · AC

Cách 1Đệ quy thử mọi cách bước – O(2^N)

Trước khi vào quy hoạch động, mình làm đúng theo cách "ngây thơ" nhất để các bạn thấy rõ bản chất bài toán. Gọi $dem(i)$ là số cách đi từ bậc $i$ lên tới sàn nhà (bậc $N$). Đứng ở bậc $i$ thì Bờm có đúng 2 lựa chọn: bước lên $i + 1$ hoặc lên $i + 2$. Vậy:

Đệ quy

• Nếu $i = N$: đã lên tới sàn nhà → đếm được 1 cách.
• Nếu $i \gt N$ (bước lố) hoặc bậc $i$ bị hỏng → 0 cách.
• Ngược lại: $dem(i) = dem(i + 1) + dem(i + 2)$.

Đáp án là $dem(0)$ (bắt đầu ở sân).

Cách này đúng, nhưng mỗi lần gọi lại tách ra 2 nhánh, các nhánh lại gọi trùng nhau rất nhiều lần (ví dụ $dem(3)$ được gọi từ cả $dem(1)$ và $dem(2)$). Số lần gọi tăng như dãy Fibonacci, tức là cỡ $1.6^N$. Mình đo thử: không có bậc hỏng, $N = 40$ đã mất khoảng 6 giây, $N = 45$ chạy hơn 30 giây vẫn chưa xong. Với $N = 10^5$ thì khỏi phải bàn 😅.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int n;
bool hong[100005];

long long dem(int i){
    if(i == n) return 1;
    if(i > n || hong[i]) return 0;
    return dem(i + 1) + dem(i + 2);
}

int main(){
    int k;
    cin >> n >> k;
    while(k--){
        int x;
        cin >> x;
        hong[x] = true;
    }
    cout << dem(0) % 1000000007;
    return 0;
}

import sys
sys.setrecursionlimit(10000)

def dem(i):
    if i == n:
        return 1
    if i > n or hong[i]:
        return 0
    return dem(i + 1) + dem(i + 2)

data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
hong = [False] * (n + 2)
for x in data[2:2 + k]:
    hong[int(x)] = True
print(dem(0) % 1000000007)

Các bạn bấm Tiếp để xem các lời gọi đệ quy được "mở ra" như thế nào, để ý xem cùng một $dem(i)$ bị tính lại bao nhiêu lần nha:

C++▶ Chạy tay từng dòng codeCách 1: đệ quy dem(i) = dem(i+1) + dem(i+2), bậc hỏng trả về 0.

Dữ liệu vào (stdin) – sửa thoải mái5 1 2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int n;

5bool hong[100005];

6

7long long dem(int i){

8 if(i == n) return 1;

9 if(i > n || hong[i]) return 0;

10 return dem(i + 1) + dem(i + 2);

11}

12

13int main(){

14 int k;

15 cin >> n >> k;

16 while(k--){

17 int x;

18 cin >> x;

19 hong[x] = true;

20 }

21 cout << dem(0) % 1000000007;

22 return 0;

23}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ cho mảng đánh dấu bậc hỏng và độ sâu ngăn xếp đệ quy.
• Thời gian: mỗi lời gọi tách thành 2, số lời gọi tăng theo kiểu Fibonacci, cỡ $O(2^N)$ (chính xác hơn là khoảng $1.618^N$).

Không gian$O(N)$

Thời gian$O(2^N)$

Chỉ để hiểu bài, nộp sẽ TLE

Với $N$ chỉ cỡ 40 – 45 là đã chạy vài giây đến vài chục giây, còn $N$ lên tới $10^5$ thì chắc chắn TLE. Ngoài ra code này chỉ lấy dư ở cuối, nếu $N$ lớn (khoảng trên 90) thì số cách vượt cả long long. Nhưng nhờ cách nghĩ này ta thấy ngay: số cách tới một bậc chỉ phụ thuộc vào 2 bậc ngay sát nó, và có rất nhiều phép tính bị lặp lại → dấu hiệu của quy hoạch động.

Cách 2Quy hoạch động 4 bước – O(N)

Bài này áp dụng phương pháp Quy Hoạch Động (Dynamic Programming) để giải quyết nhé các bạn. Cho bạn nào đã biết cơ bản qua về quy hoạch động rồi thì 4 bước giải một bài toán quy hoạch động như sau.

1Bài toán con: $F[i]$ là số cách để bước từ sân (bậc $0$) lên đến bậc thứ $i$.

2Bài toán cơ sở: $F[1]$, $F[2]$ (xét kỹ bậc hỏng), các bậc hỏng có $F = 0$.

3Đáp án: $F[N]$ – số cách đi từ sân lên sàn nhà.

4Truy hồi: $F[i] = F[i - 1] + F[i - 2]$ nếu bậc $i$ không hỏng.

Bước 1: Xác định bài toán con

Gọi $F[i]$ là số cách để bước từ sân (được xem là bậc 0) lên đến bậc thứ $i$. Lưu ý chiều ở đây ngược với cách 1: cách 1 đếm "từ bậc $i$ lên sàn", còn ở đây đếm "từ sân lên bậc $i$". Hai cách nhìn đều được, nhưng nhìn "từ sân lên" thì ta tính được lần lượt từ dưới lên trên bằng một vòng lặp rất tự nhiên.

Bước 2: Xác định bài toán cơ sở

1/ Ban đầu khởi tạo tất cả các $F[i]$ (với $i \ge 3$) mang giá trị $-1$. Vì mảng khai báo trong hàm sẽ mang giá trị ngẫu nhiên tùy theo compiler (thậm chí là giá trị rác), mà phía sau ta lại cần gọi giá trị $F[i]$ ra so sánh với $0$ để biết bậc đó có hỏng không, nên cần khởi tạo một giá trị mặc định ban đầu cho chắc. Giá trị $-1$ ở đây mang nghĩa là "chưa tính, bậc này không hỏng".

2/ Giả sử bậc 1 và bậc 2 đều không bị hỏng, tức là bước lên được, thì:

• $F[1] = 1$: chỉ có 1 cách duy nhất từ sân lên bậc 1 là bước 1 bậc ($0 + 1 = 1$).
• $F[2] = 2$: có 2 cách từ sân lên bậc 2 là bước 2 bậc ($0 + 2 = 2$) hoặc bước từng bậc ($0 + 1 + 1 = 2$).

3/ Tất cả các $F[x] = 0$ với $x$ là các bậc bị hỏng được liệt kê. Tại sao lại như vậy? Vì bậc $x$ hỏng thì chẳng có cách nào đứng trên bậc $x$ đó được, nên rõ ràng $F[x] = 0$. Sau khi đánh dấu xong các bậc hỏng, ta xét lại: nếu $F[1]$ và $F[2]$ đều là 0 thì kết luận luôn đáp án là $0$. Vì đứng ở sân mỗi lần chỉ bước được 1 hoặc 2 bậc, tức là chỉ lên được bậc 1 hoặc bậc 2, mà cả hai đều hỏng thì chẳng có cách nào lên tới sàn nhà cả.

Còn bậc N thì sao?

Đề đã đảm bảo sàn nhà (bậc $N$) không bao giờ bị hỏng nên ta không cần xét $F[N]$ có bằng 0 không. Nhưng nếu gặp bài tương tự mà không có ràng buộc này thì các bạn nhớ xét để kết thúc sớm nha, vì bậc $N$ hỏng thì chẳng thể nào bước lên bậc $N$ được.

4/ Nếu điều kiện ở mục 3 không thỏa, nghĩa là $F[1]$ và $F[2]$ có ít nhất 1 cái khác 0. Ta phải xét từng trường hợp thật chặt chẽ:

• $F[1] = 0$ và $F[2] \ne 0$ (bậc 1 hỏng, bậc 2 vẫn tốt, $F[2]$ còn giữ giá trị $2$ lúc khởi tạo): giờ phải cập nhật $F[2] = 1$, vì chỉ còn đúng 1 cách là bước thẳng $0 + 2 = 2$, không còn bước từng bậc $0 + 1 + 1$ được nữa do bậc 1 đã hỏng.
• $F[1] \ne 0$ và $F[2] = 0$: không cần cập nhật gì, mọi thứ vẫn đúng – $F[1]$ vẫn là $1$.
• Cả hai khác 0: giữ nguyên như khởi tạo ($F[1] = 1$, $F[2] = 2$).

Bước 3: Xác định đáp án bài toán

Quá rõ ràng đó chính là $F[N]$, vì ta đang cần tìm số cách để bước từ dưới sân lên sàn nhà (bậc $N$).

Bước 4: Xác định công thức truy hồi

Ở bước 2 ta đã xét kỹ ràng buộc cho $F[1]$ và $F[2]$. Nếu chương trình vẫn còn chạy (chưa in 0 rồi kết thúc) thì chắc chắn ít nhất 1 trong 2 bậc đầu không hỏng. Lúc này ta xét từ bậc $i = 3$ đến bậc $N$: nếu $F[i] \ne 0$ (tức là bậc không hỏng, $F[i]$ đang là $-1$) thì Bờm chỉ có thể đến bậc $i$ từ 2 bậc ngay trước đó là $i - 1$ (bước 1) hoặc $i - 2$ (bước 2). Nên số cách đến bậc $i$ bằng số cách đến bậc $i - 1$ cộng số cách đến bậc $i - 2$:

Công thức truy hồi

$F[i] = \big(F[i - 1] + F[i - 2]\big) \bmod 1000000007$ nếu bậc $i$ không hỏng; còn nếu $F[i] = 0$ (bậc hỏng) thì bỏ qua, giữ nguyên $0$.

Do số cách có thể rất lớn nên đề chỉ cần phần dư cho $1000000007$, vì vậy mỗi lần tính $F[i]$ ta lưu luôn kết quả sau khi chia lấy dư. Hay ở chỗ: bậc hỏng có $F = 0$ nên khi cộng vào bậc phía trên thì tự động "không đóng góp cách nào", ta không cần thêm điều kiện gì nữa. Và nếu có 2 bậc hỏng liền nhau thì mọi $F$ phía trên tự động bằng $0$ hết – đúng y như thực tế là Bờm không nhảy qua nổi 2 bậc mục 😄.

Với ví dụ của đề ($N = 5$, bậc 2 hỏng): $F[1] = 1$, $F[2] = 0$, $F[3] = F[2] + F[1] = 1$, $F[4] = F[3] + F[2] = 1$, $F[5] = F[4] + F[3] = 2$. Đáp án $2$ ✅.

Minh hoạ tô từng bậc thang

Các bạn nhập $N$ và danh sách bậc hỏng rồi bấm Tiếp để xem từng ô $F[i]$ được tính từ 2 bậc bên dưới như thế nào nhé:

N Các bậc hỏng

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int F[n + 2];
    F[1] = 1;
    F[2] = 2;
    for(int i = 3; i <= n; ++i){
        F[i] = -1;
    }
    while(k--){
        int x;
        cin >> x;
        F[x] = 0;
    }
    if(F[1] == 0 && F[2] == 0){
        cout << 0;
        return 0;
    }
    else if(F[1] == 0 && F[2] != 0){
        F[2] = 1;
    }
    for(int i = 3; i <= n; ++i){
        if(F[i] != 0){
            F[i] = (F[i - 1] + F[i - 2]) % 1000000007;
        }
    }
    cout << F[n];
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
F = [-1] * (n + 2)
F[1] = 1
F[2] = 2
for x in data[2:2 + k]:
    F[int(x)] = 0
if F[1] == 0 and F[2] == 0:
    print(0)
else:
    if F[1] == 0 and F[2] != 0:
        F[2] = 1
    for i in range(3, n + 1):
        if F[i] != 0:
            F[i] = (F[i - 1] + F[i - 2]) % 1000000007
    print(F[n])

Một chỉnh sửa nhỏ: mảng F[n + 2]

Trong bài gốc mình khai báo int F[n + 1]. Khi $N = 1$ thì mảng chỉ có chỉ số $0..1$ mà code lại gán F[2] = 2 → ghi ra ngoài mảng. Mình sửa thành F[n + 2] cho an toàn, logic giữ nguyên (với $N = 1$ đáp án là $F[1] = 1$).

C++▶ Chạy tay từng dòng codeCách 2: F[i] = F[i-1] + F[i-2], bậc hỏng F = 0, xét kỹ F[1], F[2].

Dữ liệu vào (stdin) – sửa thoải mái5 1 2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 int n, k;

8 cin >> n >> k;

9 int F[n + 2];

10 F[1] = 1;

11 F[2] = 2;

12 for(int i = 3; i <= n; ++i){

13 F[i] = -1;

14 }

15 while(k--){

16 int x;

17 cin >> x;

18 F[x] = 0;

19 }

20 if(F[1] == 0 && F[2] == 0){

21 cout << 0;

22 return 0;

23 }

24 else if(F[1] == 0 && F[2] != 0){

25 F[2] = 1;

26 }

27 for(int i = 3; i <= n; ++i){

28 if(F[i] != 0){

29 F[i] = (F[i - 1] + F[i - 2]) % 1000000007;

30 }

31 }

32 cout << F[n];

33 return 0;

34}

ChậmVừaNhanhRất nhanh

Giải thích 1 số chỗ trong code: 2 dòng đầu hàm main (ios::sync_with_stdio(0); cin.tie(0);) giúp đẩy nhanh tốc độ nhập xuất nếu các bạn code C++ (các bạn cứ gõ mấy từ này lên Google là ra rất nhiều bài giải thích nhé). Bài này $K$ có thể lên tới $10^5$ số cần đọc nên kinh nghiệm là cứ thêm 2 dòng này vào cho chạy nhanh hơn.

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ để lưu mảng $F$.
• Thời gian: $O(N)$ của bước khởi tạo $-1$ cho mảng $F$ + $O(K)$ của bước đánh dấu các bậc hỏng + $O(N)$ của bước tính các $F[i]$. Theo quy tắc cộng Big-O ta lấy thành phần lớn nhất (mà $K \le N$), nên kết luận là $O(N)$.

Không gian$O(N)$

Thời gian$O(N)$

Nếu tính chính xác thì số lần lặp cả thảy khoảng $3 \cdot N$, với $N$ lớn nhất là $10^5$ thì chỉ cỡ $3 \cdot 10^5$ lần. Giới hạn 1 giây cho phép khoảng $(3 \text{ đến } 5) \cdot 10^7$, cao lắm là $10^8$ phép tính, tức là ta còn dư cả 100 đến 200 lần, nên yên tâm không bị TLE các bạn hen.

Nhớ lấy dư ngay trong vòng lặp

Không có bậc hỏng thì $F[i]$ chính là số Fibonacci, tăng cực nhanh (bậc 50 đã vượt $10^{10}$). Nên phải % 1000000007 ngay mỗi lần tính. Vì $F[i - 1], F[i - 2] \lt 10^9 + 7$ nên tổng của chúng nhỏ hơn $2.000.000.014$ – vẫn vừa trong int (tối đa khoảng $2.147 \cdot 10^9$), nên dùng int như code trên là an toàn.

Ghi chú của mình: code C++ và Python của cả 2 cách ở trên đều cho đúng output của ví dụ đề, và đã được so với code vét cạn (thử mọi tập bậc dừng chân) trên 500 bộ test ngẫu nhiên nhỏ ($N \le 14$, có cả test nhiều bậc hỏng liền nhau, bậc 1 – 2 hỏng, bậc hỏng bị lặp lại) – khớp hết. Với $N = 10^5$, cách 2 bản C++ chạy chưa tới 0.1 giây, bản Python khoảng 0.6 giây; còn cách 1 (đệ quy) với $N = 45$ đã chạy quá 30 giây đúng như phân tích.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇