Bài học

Trạng thái, cơ sở và công thức chuyển trạng thái

Mục tiêu bài học

Sau bài này, em tự thiết kế được một hàm đệ quy từ đầu bằng một khung ba phần rõ ràng — không còn dừng lại ở việc nhớ sẵn công thức fib(n) = fib(n-1) + fib(n-2) hay n! = n·(n-1)! như ở lớp 10. Đây là kỹ năng nền cho toàn bộ khoá này: mọi kỹ thuật quay lui và cắt tỉa ở các bài sau đều bắt đầu từ việc thiết kế đúng một hàm đệ quy.

Cần nhớ trước

Em cần vững hai điều đã học ở lớp 10: đệ quy là một hàm gọi lại chính nó với đầu vào nhỏ hơn, và mỗi lời gọi hàm — kể cả lời gọi đệ quy — được Python lưu trên một cấu trúc gọi là ngăn xếp lời gọi (call stack), chỉ giải phóng khi hàm đó return.

Khi nào 'hàm tự gọi chính nó' là chưa đủ

Đề chuẩn lớp 10 luôn cho sẵn công thức đệ quy — tính giai thừa, tính fib(n), đếm ước số — việc của em chỉ là dịch công thức đó sang code. Đề HSG làm ngược lại: cho một bài toán chưa từng gặp, không có công thức đệ quy viết sẵn trong đề, và em phải tự dựng ra công thức đó trước khi viết được một dòng code nào.

Khung thiết kế ba phần

Mọi hàm đệ quy đúng đều trả lời được ba câu hỏi, theo đúng thứ tự. Một, trạng thái: đại lượng nhỏ nhất mô tả đầy đủ một bài toán con — với fib chỉ cần một số nguyên $n$ , không cần gì thêm. Hai, trường hợp cơ sở: đầu vào nhỏ nhất mà em giải được ngay, không cần đệ quy. Ba, công thức chuyển trạng thái: cách biểu diễn bài toán ở trạng thái hiện tại qua một hoặc nhiều bài toán con có trạng thái NHỎ HƠN NGHIÊM NGẶT. Chữ nghiêm ngặt quan trọng: nếu trạng thái con không nhỏ hơn thật sự, đệ quy sẽ không bao giờ dừng.

Mọi hàm đệ quy đúng đều trả lời được ba câu hỏi, theo đúng thứ tự. Một, **trạng thái**: đại lượng nhỏ nhất mô tả đầy đủ một bài toán con — với fib chỉ cần một số nguyên $n$, không cần gì thêm. Hai, **trường hợp cơ sở**: đầu vào nhỏ nhất mà em giải được ngay, không cần đệ quy. Ba, **công thức chuyển trạng thái**: cách biểu diễn bài toán ở trạng thái hiện tại qua một hoặc nhiều bài toán con có trạng thái NHỎ HƠN NGHIÊM NGẶT. Chữ nghiêm ngặt quan trọng: nếu trạng thái con không nhỏ hơn thật sự, đệ quy sẽ không bao giờ dừng.

Bài toán mở đầu

Thử chạy hai cách tính fib(30). Cách một, đệ quy ngây thơ: fib(n) gọi fib(n-1) rồi fib(n-2), không lưu lại gì cả. Cách hai, đệ quy có nhớ kết quả từng trạng thái đã tính. Chạy thật bằng Python: cách một tốn 2,692,537 lời gọi hàm để ra kết quả, cách hai chỉ tốn 59 lời gọi — cùng một bài toán, cùng đúng một công thức, chênh nhau khoảng 45,636 lần. Vì sao dùng đúng công thức mà một cách tức thì, một cách gần như treo máy?

Ý tưởng cốt lõi — trạng thái trùng lặp

Lý do nằm ở cách cây gọi đệ quy nhánh ra. Khi tính fib(5), hàm gọi fib(4) và fib(3); nhưng fib(4) bên trong nó lại gọi fib(3) một lần nữa — trạng thái fib(3) bị tính LẶP LẠI ở hai nhánh khác nhau của cây gọi. Càng n lớn, số lần trùng lặp càng tăng theo cấp số nhân. Bộ nhớ hoá (memoization) chặn đứng sự trùng lặp đó: trước khi tính fib(n), tra trong một dict xem trạng thái $n$ đã có kết quả chưa; nếu có, trả về ngay, không đệ quy lại; nếu chưa, tính rồi lưu vào dict trước khi trả về.

Lý do nằm ở cách cây gọi đệ quy nhánh ra. Khi tính fib(5), hàm gọi fib(4) và fib(3); nhưng fib(4) bên trong nó lại gọi fib(3) một lần nữa — trạng thái fib(3) bị tính LẶP LẠI ở hai nhánh khác nhau của cây gọi. Càng n lớn, số lần trùng lặp càng tăng theo cấp số nhân. Bộ nhớ hoá (memoization) chặn đứng sự trùng lặp đó: trước khi tính fib(n), tra trong một `dict` xem trạng thái $n$ đã có kết quả chưa; nếu có, trả về ngay, không đệ quy lại; nếu chưa, tính rồi lưu vào `dict` trước khi trả về.

Ví dụ

Ví dụ 1 — Từ trạng thái đến bộ nhớ hoá: dãy Fibonacci

1
Đề chuẩn lớp 10 chỉ yêu cầu viết fib(n) = fib(n-1) + fib(n-2) — công thức có sẵn. Đề HSG hỏi khác: fib(30) chạy bằng đệ quy thường mất bao lâu, và làm sao để nó chạy nhanh mà KHÔNG đổi công thức toán học? Đây là câu hỏi về hiệu năng cài đặt, không phải về công thức.
2
Ba phần thiết kế: trạng thái là số nguyên $n$ ; trường hợp cơ sở là $n \le 1$ (trả về chính $n$ , vì fib(0)=0, fib(1)=1); công thức chuyển trạng thái là fib(n) = fib(n-1) + fib(n-2) — hai bài toán con đều có trạng thái nhỏ hơn $n$ . Bộ nhớ hoá thêm một dict memo lưu kết quả của mỗi trạng thái đã tính.
Ba phần thiết kế: trạng thái là số nguyên $n$; trường hợp cơ sở là $n \le 1$ (trả về chính $n$, vì fib(0)=0, fib(1)=1); công thức chuyển trạng thái là fib(n) = fib(n-1) + fib(n-2) — hai bài toán con đều có trạng thái nhỏ hơn $n$. Bộ nhớ hoá thêm một `dict memo` lưu kết quả của mỗi trạng thái đã tính.

def fib_khong_nho(n):
    if n <= 1:
        return n
    return fib_khong_nho(n - 1) + fib_khong_nho(n - 2)

def fib_co_nho(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_co_nho(n - 1, memo) + fib_co_nho(n - 2, memo)
    return memo[n]

4
Chạy trên máy và đếm số lời gọi hàm: fib(5) tốn 15 lời gọi không nhớ, 9 lời gọi có nhớ. fib(10): 177 so với 19. fib(30): 2,692,537 so với 59 — không nhớ tăng theo cấp số nhân xấp xỉ $2^n$ , có nhớ tăng TUYẾN TÍNH theo $n$ vì mỗi trạng thái chỉ tính đúng một lần.
Chạy trên máy và đếm số lời gọi hàm: fib(5) tốn 15 lời gọi không nhớ, 9 lời gọi có nhớ. fib(10): 177 so với 19. fib(30): 2,692,537 so với 59 — không nhớ tăng theo cấp số nhân xấp xỉ $2^n$, có nhớ tăng TUYẾN TÍNH theo $n$ vì mỗi trạng thái chỉ tính đúng một lần.
5
Số lời gọi có nhớ luôn xấp xỉ $2n-1$ — mỗi trạng thái từ $0$ đến $n$ được tính đúng một lần, cộng thêm các lần tra dict không trúng — tức O(n), so với O( $2^n$ ) của bản không nhớ. Bất kỳ hàm đệ quy nào có TRẠNG THÁI TRÙNG LẶP, không riêng gì Fibonacci, đều nên xét bộ nhớ hoá trước khi tối ưu bằng cách khác.
Số lời gọi có nhớ luôn xấp xỉ $2n-1$ — mỗi trạng thái từ $0$ đến $n$ được tính đúng một lần, cộng thêm các lần tra `dict` không trúng — tức O(n), so với O($2^n$) của bản không nhớ. Bất kỳ hàm đệ quy nào có TRẠNG THÁI TRÙNG LẶP, không riêng gì Fibonacci, đều nên xét bộ nhớ hoá trước khi tối ưu bằng cách khác.
6
Ta có fib(n) với trạng thái $n$ , trường hợp cơ sở $n \le 1$ trả về $n$ , công thức chuyển trạng thái fib(n) = fib(n-1) + fib(n-2). Không nhớ, mỗi lời gọi sinh hai lời gọi con nên tổng số lời gọi tăng theo cấp số nhân theo $n$ . Thêm memo: mỗi trạng thái $n$ chỉ tính một lần, vì lần gọi thứ hai tra dict và trả về ngay, không đệ quy tiếp. Do đó tổng số lời gọi giảm từ hàm mũ xuống tuyến tính. Vậy bộ nhớ hoá không đổi kết quả — vẫn đúng công thức fib(n) = fib(n-1) + fib(n-2) — chỉ đổi SỐ LẦN mỗi trạng thái được tính.
Ta có fib(n) với trạng thái $n$, trường hợp cơ sở $n \le 1$ trả về $n$, công thức chuyển trạng thái fib(n) = fib(n-1) + fib(n-2). Không nhớ, mỗi lời gọi sinh hai lời gọi con nên tổng số lời gọi tăng theo cấp số nhân theo $n$. Thêm memo: mỗi trạng thái $n$ chỉ tính một lần, vì lần gọi thứ hai tra `dict` và trả về ngay, không đệ quy tiếp. Do đó tổng số lời gọi giảm từ hàm mũ xuống tuyến tính. Vậy bộ nhớ hoá không đổi kết quả — vẫn đúng công thức fib(n) = fib(n-1) + fib(n-2) — chỉ đổi SỐ LẦN mỗi trạng thái được tính.

Số lời gọi không nhớ tăng theo cấp số nhân; có nhớ gần như phẳng — đúng bằng

2n-1

mỗi trường hợp.Số lời gọi không nhớ tăng theo cấp số nhân; có nhớ gần như phẳng — đúng bằng $2n-1$ mỗi trường hợp.

Mỗi cột là một trạng thái đã được lưu — lần tra cứu sau chỉ cần đọc cột này, không tính lại.

Khung ba phần này không riêng gì cho Fibonacci — nó dùng được cho MỌI bài toán mà lời giải một trạng thái phụ thuộc vào lời giải của trạng thái nhỏ hơn. Bài toán đếm bước leo cầu thang dưới đây trông chẳng liên quan gì tới dãy số, nhưng khi soi qua đúng khung ba phần, nó lộ ra là CÙNG một công thức.

Ví dụ

Ví dụ 2 — Nhận ra cùng một trạng thái ở bài toán khác: đếm cách leo cầu thang

1
Đề chuẩn hỏi trực tiếp: viết công thức fib(n). Đề HSG không nhắc gì tới Fibonacci: Một cầu thang có $n$ bậc, mỗi bước em bước lên 1 hoặc 2 bậc. Có bao nhiêu cách leo hết cầu thang? Em phải TỰ NHẬN RA đây là cùng dạng bài toán — đề không gợi ý sẵn.
Đề chuẩn hỏi trực tiếp: viết công thức fib(n). Đề HSG không nhắc gì tới Fibonacci: Một cầu thang có $n$ bậc, mỗi bước em bước lên 1 hoặc 2 bậc. Có bao nhiêu cách leo hết cầu thang? Em phải TỰ NHẬN RA đây là cùng dạng bài toán — đề không gợi ý sẵn.
2
Áp khung ba phần cho bài mới: trạng thái là số bậc còn lại $n$ ; trường hợp cơ sở $f(1)=1$ (một cách: bước 1 bậc), $f(2)=2$ (hai cách: 1+1 hoặc bước thẳng 2); công thức chuyển trạng thái: bước CUỐI CÙNG lên tới bậc $n$ hoặc là một bước 1 bậc từ bậc $n-1$ , hoặc là một bước 2 bậc từ bậc $n-2$ , nên $f(n) = f(n-1) + f(n-2)$ .
Áp khung ba phần cho bài mới: trạng thái là số bậc còn lại $n$; trường hợp cơ sở $f(1)=1$ (một cách: bước 1 bậc), $f(2)=2$ (hai cách: 1+1 hoặc bước thẳng 2); công thức chuyển trạng thái: bước CUỐI CÙNG lên tới bậc $n$ hoặc là một bước 1 bậc từ bậc $n-1$, hoặc là một bước 2 bậc từ bậc $n-2$, nên $f(n) = f(n-1) + f(n-2)$.
3
Không phải trùng hợp: bất kỳ bài toán đếm số cách nào mà bước cuối cùng chỉ có một số lựa chọn cố định (ở đây là 2 lựa chọn: 1 bậc hoặc 2 bậc), và bài toán con sau khi bỏ bước cuối vẫn giữ nguyên cấu trúc, đều dẫn tới một công thức truy hồi tuyến tính kiểu Fibonacci. Hỏi 'bước cuối cùng có mấy lựa chọn' là chìa khoá để tự dựng công thức chuyển trạng thái cho một bài toán đếm mới.
Không phải trùng hợp: bất kỳ bài toán đếm số cách nào mà bước cuối cùng chỉ có một số lựa chọn cố định (ở đây là 2 lựa chọn: 1 bậc hoặc 2 bậc), và bài toán con sau khi bỏ bước cuối vẫn giữ nguyên cấu trúc, đều dẫn tới một công thức truy hồi tuyến tính kiểu Fibonacci. Hỏi 'bước cuối cùng có mấy lựa chọn' là chìa khoá để tự dựng công thức chuyển trạng thái cho một bài toán đếm mới.
4
Chạy bằng Python với bộ nhớ hoá: $f(10) = 89$ cách. Kiểm tra tay với $n$ nhỏ: $f(3) = f(2)+f(1) = 2+1 = 3$ (ba cách: 1+1+1, 1+2, 2+1) — khớp với chương trình.
Chạy bằng Python với bộ nhớ hoá: $f(10) = 89$ cách. Kiểm tra tay với $n$ nhỏ: $f(3) = f(2)+f(1) = 2+1 = 3$ (ba cách: 1+1+1, 1+2, 2+1) — khớp với chương trình.
5
Đổi luật: mỗi bước được lên 1, 2 hoặc 3 bậc. Bước cuối giờ có BA lựa chọn thay vì hai, nên công thức trở thành $f(n) = f(n-1)+f(n-2)+f(n-3)$ , với cơ sở $f(0)=1$ , $f(1)=1$ , $f(2)=2$ . Chạy chương trình: $f(6) = 24$ cách — đúng khung ba phần cũ, chỉ đổi số lượng lựa chọn ở bước cuối.
Đổi luật: mỗi bước được lên 1, 2 hoặc 3 bậc. Bước cuối giờ có BA lựa chọn thay vì hai, nên công thức trở thành $f(n) = f(n-1)+f(n-2)+f(n-3)$, với cơ sở $f(0)=1$, $f(1)=1$, $f(2)=2$. Chạy chương trình: $f(6) = 24$ cách — đúng khung ba phần cũ, chỉ đổi số lượng lựa chọn ở bước cuối.
6
Ta có trạng thái là số bậc còn lại. Do bước cuối cùng của một cách leo hợp lệ chỉ có thể là bước 1 bậc hoặc bước 2 bậc, nên số cách leo tới bậc $n$ bằng tổng số cách leo tới bậc $n-1$ (rồi bước 1) và số cách leo tới bậc $n-2$ (rồi bước 2). Với cơ sở $f(1)=1$ , $f(2)=2$ , suy ra $f(n)=f(n-1)+f(n-2)$ với mọi $n \ge 3$ . Vậy công thức đúng bằng đúng công thức Fibonacci, dù đề bài không hề nhắc tới dãy số này.
Ta có trạng thái là số bậc còn lại. Do bước cuối cùng của một cách leo hợp lệ chỉ có thể là bước 1 bậc hoặc bước 2 bậc, nên số cách leo tới bậc $n$ bằng tổng số cách leo tới bậc $n-1$ (rồi bước 1) và số cách leo tới bậc $n-2$ (rồi bước 2). Với cơ sở $f(1)=1$, $f(2)=2$, suy ra $f(n)=f(n-1)+f(n-2)$ với mọi $n \ge 3$. Vậy công thức đúng bằng đúng công thức Fibonacci, dù đề bài không hề nhắc tới dãy số này.

Bẫy thường gặp

Ba bẫy thường gặp. (1) Quên trường hợp cơ sở cho TẤT CẢ giá trị nhỏ cần thiết — fib cần cả $f(0)$ lẫn $f(1)$ , thiếu một trong hai làm sai toàn bộ dãy. (2) Trạng thái con không giảm nghiêm ngặt — ví dụ lỡ viết fib(n-1) hai lần thay vì fib(n-1) và fib(n-2) — khiến đệ quy không bao giờ chạm trường hợp cơ sở. (3) Bẫy rất riêng của Python: đặt memo={} làm giá trị mặc định của tham số. dict mặc định đó CHỈ được tạo một lần duy nhất, lúc hàm được định nghĩa, rồi dùng lại cho MỌI lần gọi sau — kể cả khi input đã đổi hoàn toàn. Chạy thử: với mảng chi phí A, hàm memo hoá kiểu này trả về 15 (đúng); gọi tiếp với một mảng chi phí B khác hẳn, hàm vẫn trả về 15 — SAI, vì nó tái sử dụng memo cũ của mảng A. Sửa bằng cách đặt memo=None làm mặc định rồi tạo dict mới bên trong hàm; làm đúng, kết quả cho mảng B là 6.

Ba bẫy thường gặp. (1) Quên trường hợp cơ sở cho TẤT CẢ giá trị nhỏ cần thiết — fib cần cả $f(0)$ lẫn $f(1)$, thiếu một trong hai làm sai toàn bộ dãy. (2) Trạng thái con không giảm nghiêm ngặt — ví dụ lỡ viết fib(n-1) hai lần thay vì fib(n-1) và fib(n-2) — khiến đệ quy không bao giờ chạm trường hợp cơ sở. (3) Bẫy rất riêng của Python: đặt `memo={}` làm giá trị mặc định của tham số. `dict` mặc định đó CHỈ được tạo một lần duy nhất, lúc hàm được định nghĩa, rồi dùng lại cho MỌI lần gọi sau — kể cả khi input đã đổi hoàn toàn. Chạy thử: với mảng chi phí A, hàm memo hoá kiểu này trả về 15 (đúng); gọi tiếp với một mảng chi phí B khác hẳn, hàm vẫn trả về 15 — SAI, vì nó tái sử dụng memo cũ của mảng A. Sửa bằng cách đặt `memo=None` làm mặc định rồi tạo `dict` mới bên trong hàm; làm đúng, kết quả cho mảng B là 6.

Luyện tập có hướng dẫn

Luyện tập độc lập

Thử thách

Ghi nhớ

Ba câu hỏi để nhớ mãi: bài toán con nhỏ nhất tự giải được là gì (cơ sở), một trạng thái phụ thuộc bài toán con nào (chuyển trạng thái), và trạng thái nào bị tính lặp lại nhiều lần (bộ nhớ hoá). Ba câu hỏi này áp dụng được cho mọi hàm đệ quy trong khoá — không chỉ cho các ví dụ đã gặp.

Bài sau vẫn dùng đúng khung ba phần này, nhưng đổi loại trạng thái: thay vì một số nguyên $n$ , trạng thái sẽ là MỘT PHẦN của một cấu hình đang được xây dựng — ví dụ một hoán vị đang dựng dở. Khi đó, 'công thức chuyển trạng thái' không còn là một phép cộng đơn giản, mà là một vòng lặp thử từng lựa chọn tại chỗ rồi đệ quy tiếp — bước đệm trực tiếp sang quay lui ở Chương 4.

Bài sau vẫn dùng đúng khung ba phần này, nhưng đổi loại trạng thái: thay vì một số nguyên $n$, trạng thái sẽ là MỘT PHẦN của một cấu hình đang được xây dựng — ví dụ một hoán vị đang dựng dở. Khi đó, 'công thức chuyển trạng thái' không còn là một phép cộng đơn giản, mà là một vòng lặp thử từng lựa chọn tại chỗ rồi đệ quy tiếp — bước đệm trực tiếp sang quay lui ở Chương 4.