Khóa học Python từ Cơ bản đến Nâng cao

Bài 10.5 - Kỹ thuật memoization trong Python

Memoization là kỹ thuật lưu trữ kết quả các hàm đã tính trước đó để tránh tính lại, từ đó tăng tốc độ chương trình rõ rệt, đặc biệt với các bài toán đệ quy.

Ví dụ vấn đề: Fibonacci đệ quy thuần

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

Chạy fib(30) sẽ rất chậm vì hàm fib(n) bị gọi lại rất nhiều lần với cùng tham số.

Cách dùng memoization thủ công

Ta dùng một dictionary để lưu kết quả đã tính:

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

Ví dụ:

print(fib_memo(30))  # Output: 832040, rất nhanh

Từ O(2^n) giảm còn O(n), tiết kiệm hàng triệu phép tính với n lớn.

Cách dùng functools.lru_cache trong Python

Thư viện functools có sẵn decorator để tự động memo hóa:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Ví dụ:

print(fib(50))  # Output: 12586269025

@lru_cache giúp memo hóa hàm đơn giản chỉ bằng 1 dòng.

Memoization với bài toán khác: Tính số cách leo cầu thang

Đề bài: Mỗi lần có thể bước 1 hoặc 2 bậc. Có bao nhiêu cách để leo lên n bậc?

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

Thử chạy:

print(climb(10))  # Output: 89

Khi nào nên dùng memoization?

• Hàm đệ quy có gọi lại nhiều lần cùng tham số
• Bài toán có tính chồng lặp trạng thái
• Không cần phải tối ưu bộ nhớ quá khắt khe

Không nên dùng memoization khi:

• Bài toán không có lặp lại trạng thái
• Cần tính toán chính xác từng bước (ví dụ yêu cầu thứ tự cụ thể)
• Tối ưu về bộ nhớ (vì memo hóa chiếm RAM)

Tổng kết

• Memoization là kỹ thuật cực kỳ hữu ích khi viết các bài toán đệ quy.
• Có thể dùng dict hoặc @lru_cache đều được.
• Ghi nhớ để dùng cho các bài như: Fibonacci, leo cầu thang, LCS, LIS, subset sum, knapsack,...