DSA Interview Prep · Pelajaran

Memoisasi: Menyimpan Keputusan Rekursif

Gunakan @functools.lru_cache dan kamus memo manual pada Fibonacci serta climbing-stairs untuk menghapuskan pengiraan semula eksponen.

Pelajaran 4 daripada 413 langkah

Memoisasi: Menyimpan Keputusan Rekursif ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Masalah Rekursi Berlebihan

Fibonacci rekursif naif mengira nilai yang sama berulang kali. fib(5) memanggil fib(4) dan fib(3); fib(4) memanggil fib(3) dan fib(2) — jadi fib(3) dikira dua kali. Lebihan ini berkembang secara eksponen: fib(40) menghasilkan lebih daripada satu bilion panggilan fungsi. Memoisasi menyelesaikan masalah ini dengan menyimpan setiap hasil pada kali pertama ia dikira, supaya panggilan seterusnya mendapatkannya dalam O(1) dan bukannya mengiranya semula.

# Count calls without memoisation
call_count = [0]

def fib_plain(n):
    call_count[0] += 1
    if n <= 1: return n
    return fib_plain(n-1) + fib_plain(n-2)

fib_plain(20)
print(f'fib(20) without memo: {call_count[0]:,} calls')
# ~21,891 calls for n=20; ~1 billion for n=40

Memoisasi Manual dengan Kamus

Tambahkan kamus memo sebagai parameter (atau gunakan fungsi penutup). Sebelum melakukan pengiraan, semak sama ada jawapan itu sudah ada dalam memo. Jika ya, pulangkannya serta-merta. Jika tidak, kirakannya, simpan dalam memo dan pulangkan hasilnya. Setiap submasalah unik kini dikira tepat sekali, lalu menukarkan masa O(2^n) kepada O(n) dan menggunakan ruang O(n) untuk kamus memo serta ruang tindanan O(n).

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

print(fib_memo(10))   # 55
print(fib_memo(50))   # 12586269025
print(fib_memo(100))  # huge number — still fast!

Penghias functools.lru_cache

Python menyediakan @functools.lru_cache(maxsize=None) (juga tersedia sebagai @functools.cache dalam Python 3.9+) untuk mengautomasikan memoisasi. Menambahkan penghias ini di atas sesuatu fungsi akan menyimpan semua panggilan berdasarkan argumennya. maxsize=None bermaksud saiz tembolok tidak terhad — setiap gabungan argumen unik disimpan dalam tembolok. Ini menukar sebarang fungsi rekursif kepada versi yang dimemoisasi dengan satu baris kod.

import functools

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

print(fib(50))   # 12586269025
print(fib(100))  # 354224848179261915075
print(fib.cache_info())  # CacheInfo(hits=..., misses=..., maxsize=None, currsize=...)

Mendaki Tangga (LeetCode 70)

LeetCode 70 'Mendaki Tangga': anda boleh menaiki 1 atau 2 anak tangga pada satu-satu masa. Berapakah bilangan cara untuk sampai ke anak tangga n? Ini sebenarnya Fibonacci yang disamarkan: ways(n) = ways(n-1) + ways(n-2). Kes asas: ways(0) = 1 (satu cara untuk kekal di aras tanah), ways(1) = 1. Dengan memoisasi, masa ialah O(n) dan ruang ialah O(n).

import functools

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

for i in range(1, 8):
    print(f'climbStairs({i}) = {climbStairs(i)}')
# 1,2,3,5,8,13,21

Pertukaran Syiling (LeetCode 322)

LeetCode 322 'Pertukaran Syiling': diberikan denominasi dan jumlah sasaran, cari bilangan minimum syiling. Rekursi memoisasi atas-ke-bawah: dp(amount) = 1 + min(dp(amount - coin)) untuk setiap syiling yang sah. Kes asas: dp(0) = 0. Simpan setiap subjumlah dalam tembolok. Jika sesuatu subjumlah mustahil dicapai, pulangkan infiniti. Memoisasi menukarkan kaedah cuba semua yang eksponen kepada masa O(amount × len(coins)).

import functools

def coinChange(coins, amount):
    @functools.lru_cache(maxsize=None)
    def dp(rem):
        if rem == 0:
            return 0
        if rem < 0:
            return float('inf')
        return 1 + min(dp(rem - c) for c in coins)

    result = dp(amount)
    return result if result != float('inf') else -1

print(coinChange([1, 5, 11], 15))  # 3 (5+5+5)
print(coinChange([1, 2, 5], 11))   # 3 (5+5+1)
print(coinChange([2], 3))          # -1

Pemisahan Perkataan (LeetCode 139) dengan Memoisasi

LeetCode 139 'Pemisahan Perkataan': tentukan sama ada sesuatu rentetan boleh dibahagikan kepada perkataan dalam kamus. Rekursi atas-ke-bawah: can_break(s, start) mencuba setiap awalan s[start:end]; jika awalan itu terdapat dalam kamus dan can_break(s, end) ialah benar, pulangkan benar. Tanpa memoisasi, kerumitannya ialah O(2^n); dengan memoisasi (menyimpan setiap indeks mula), kerumitannya menjadi O(n² × L), dengan L ialah panjang perkataan maksimum.

import functools

def wordBreak(s, wordDict):
    word_set = set(wordDict)

    @functools.lru_cache(maxsize=None)
    def can_break(start):
        if start == len(s):
            return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and can_break(end):
                return True
        return False

    return can_break(0)

print(wordBreak('leetcode', ['leet', 'code']))    # True
print(wordBreak('applepenapple', ['apple','pen'])) # True
print(wordBreak('catsandog', ['cats','dog','sand','and','cat']))  # False

Memoisasi berbanding Tabulasi

Memoisasi (atas-ke-bawah) bermula dengan masalah asal dan menyimpan jawapan apabila jawapan itu ditemui secara rekursif. Ia hanya menyelesaikan submasalah yang benar-benar diperlukan. Tabulasi (bawah-ke-atas) mengisi jadual terlebih dahulu, daripada submasalah kecil kepada yang besar, lalu menyelesaikan semua submasalah tanpa mengira keperluannya. Memoisasi lebih mudah diterbitkan daripada penyelesaian rekursif; tabulasi mengelakkan had kedalaman rekursi dan overhed panggilan fungsi.

# Memoisation (top-down)
import functools
@functools.lru_cache(maxsize=None)
def fib_td(n):
    if n <= 1: return n
    return fib_td(n-1) + fib_td(n-2)

# Tabulation (bottom-up)
def fib_bu(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fib_td(20), fib_bu(20))   # 6765 6765
# Both O(n) time; fib_bu avoids recursion limit

Pengoptimuman Ruang: Pemboleh Ubah Bergilir

Banyak masalah DP yang diselesaikan oleh rekursi memoisasi dalam ruang O(n) boleh dioptimumkan lagi kepada ruang O(1) apabila hanya sejumlah tetap jawapan submasalah terdahulu diperlukan. Untuk Fibonacci, hanya dua nilai terakhir yang penting. Begitu juga untuk mendaki tangga. Dua pemboleh ubah bergilir menggantikan keseluruhan kamus memo atau jadual.

# Fibonacci with O(1) space
def fib_o1(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

for i in range(8):
    print(f'fib({i})={fib_o1(i)}', end='  ')
print()

# Climbing stairs O(1) space
def climbStairs_o1(n):
    if n <= 1: return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
print(climbStairs_o1(10))  # 89

lru_cache berbanding Fungsi Penutup berbanding Kamus Global

Terdapat tiga cara untuk melaksanakan memoisasi secara manual. kamus global adalah mudah, tetapi mencemarkan skop modul. fungsi penutup merangkumkan tembolok dalam fungsi, lalu mencegah kebocoran tetapi memerlukan pembalut. @lru_cache ialah pilihan paling kemas — satu penghias menggantikan semua kod rangka. Dalam konteks temu duga, mulakan dengan @lru_cache melainkan penemu duga meminta pelaksanaan manual secara khusus.

import functools

# 1. Global dict (messy)
memo_global = {}
def fib_global(n):
    if n in memo_global: return memo_global[n]
    if n <= 1: return n
    memo_global[n] = fib_global(n-1) + fib_global(n-2)
    return memo_global[n]

# 2. Closure (cleaner scope)
def make_fib():
    cache = {}
    def fib(n):
        if n in cache: return cache[n]
        if n <= 1: return n
        cache[n] = fib(n-1) + fib(n-2)
        return cache[n]
    return fib
fib_closure = make_fib()

# 3. lru_cache (best)
@functools.lru_cache(maxsize=None)
def fib_cached(n):
    if n <= 1: return n
    return fib_cached(n-1) + fib_cached(n-2)

print(fib_global(30), fib_closure(30), fib_cached(30))  # all 832040

Apabila Memoisasi Tidak Membantu

Memoisasi hanya mempercepat masalah yang mempunyai submasalah bertindih — kes yang sama submasalahnya dikira berulang kali. Jika setiap submasalah unik, seperti dalam pelintasan pepohon mudah yang melawati setiap nod tepat sekali, memoiasi menambah overhed tanpa manfaat. Selain itu, memoisasi tidak dapat membaiki masalah apabila pertumbuhan pepohon rekursif adalah eksponen terhadap bilangan submasalah berbeza, bukannya disebabkan penggunaan semula — masalah tersebut memerlukan algoritma yang sama sekali berbeza.

# Memoisation DOES help: overlapping sub-problems (Fibonacci)
# fib(n) reuses fib(n-2), fib(n-3), etc.

# Memoisation does NOT help: distinct sub-problems (permutations)
# Each unique (remaining_elements, target) pair is truly distinct
# The exponential complexity comes from the state space itself

print('Memoisation: useful when SAME sub-problem recurs multiple times')
print('Not useful: when every sub-problem is unique to one recursive path')

Ringkasan: Senarai Semak Memoisasi

Gunakan memoisasi apabila: anda mempunyai penyelesaian rekursif yang betul tetapi perlahan disebabkan pengiraan semula yang berlebihan, fungsi itu mempunyai sebilangan kecil gabungan argumen yang berbeza, dan nilai kembaliannya hanya bergantung pada argumen (fungsi tulen — tiada kesan sampingan dan tiada keadaan global). Semak ruang keadaan submasalah: jika terdapat paling banyak O(n) atau O(n²) keadaan yang berbeza, memoisation menukarkan masa eksponen kepada masa polinomial.

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Imbas Kembali Pelajaran

Dalam pelajaran ini, anda mempelajari bahawa: memoisasi menyimpan hasil submasalah untuk mengelakkan pengiraan semula, lalu menukarkan rekursi eksponen kepada masa polinomial, @functools.lru_cache ialah alat Python idiomatik yang hanya memerlukan satu baris, dan memoisasi (atas-ke-bawah) serta tabulasi (bawah-ke-atas) ialah dua gaya DP — memoisasi lebih mudah diterbitkan, manakala tabulasi mengelakkan masalah kedalaman tindanan. Tahniah — anda telah melengkapkan modul rekursi dan peta cincang!

Percuma untuk bermula

Pelajari Python dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 30
Pelajaran: 120

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Memoisasi: Menyimpan Keputusan Rekursif” percuma?

Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Memoisasi: Menyimpan Keputusan Rekursif”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Memoisasi: Menyimpan Keputusan Rekursif”?

Gunakan @functools.lru_cache dan kamus memo manual pada Fibonacci serta climbing-stairs untuk menghapuskan pengiraan semula eksponen. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?

Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.

Berapa lamakah pelajaran “Memoisasi: Menyimpan Keputusan Rekursif” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

Rangka Kerja Rekursi: Kes Asas, Kepercayaan, Binaan
Menggambarkan Tindanan Panggilan
Pertukaran Rekursif dan Lelaran
Memoisasi: Menyimpan Keputusan Rekursif

← Kembali ke DSA Interview Prep