0Pricing
DSA Interview Prep · Pelajaran

DP Bottom-Up dengan Tabulasi

Ubah solusi top-down menjadi tabel DP iteratif, lalu kurangi ruang dari O(n) menjadi O(1) ketika hanya beberapa entri terakhir yang diperlukan.

DP Bottom-Up dengan Tabulasi adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.

DP dari Bawah ke Atas: Pendekatan Tabulasi

DP dari bawah ke atas (tabulasi) mengisi tabel jawaban submasalah mulai dari submasalah terkecil dan membangunnya hingga mencapai jawaban. Alih-alih melakukan rekursi ke bawah dan menyimpan hasil saat kembali ke atas, Anda menghitungnya secara iteratif dari dasar. Tabel tersebut biasanya berupa larik 1D atau 2D, dengan setiap sel dihitung berdasarkan sel-sel yang telah diisi sebelumnya. Ini menghilangkan rekursi sepenuhnya — tidak ada tumpukan pemanggilan, tidak ada batas rekursi, dan lokalitas memori yang lebih baik.

# Converting top-down to bottom-up:
# Top-down: start at fib(n), recurse to smaller, cache
# Bottom-up: start at fib(0), fill table to fib(n)

# Key question for bottom-up:
# 'In what order do I fill the table so that when I compute dp[i],
# all values dp[i] depends on are already filled?'
# For Fibonacci: dp[i] needs dp[i-1] and dp[i-2]
# Fill order: i = 2, 3, 4, ..., n (left to right)
print('Bottom-up: fill small sub-problems first, build to answer')

Fibonacci dari Bawah ke Atas

Fibonacci dari bawah ke atas mengisi dp[0..n] dari kiri ke kanan. dp[i] = dp[i-1] + dp[i-2] untuk i >= 2. Kasus dasarnya adalah dp[0] = 0 dan dp[1] = 1, yang disimpan langsung dalam larik. Waktunya O(n) dan ruangnya O(n) untuk tabel lengkap. Setelah Anda melihat bahwa dp[i] hanya bergantung pada dua nilai terakhir, Anda dapat mengurangi ruang menjadi O(1) dengan dua variabel — inilah langkah optimisasi ruang.

def fib_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0  # base case
    dp[1] = 1  # base case
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print([fib_bottom_up(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

# Space-optimised to O(1):
def fib_optimised(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_optimised(50))  # 12586269025

Penukaran Koin dari Bawah ke Atas

Untuk penukaran koin, tabel dari bawah ke atas adalah dp[0..amount], dengan dp[i] = jumlah minimum koin untuk membentuk jumlah amount i. Inisialisasikan dp[0] = 0 (nol koin untuk jumlah nol) dan dp[1..amount] = tak terhingga. Untuk setiap jumlah i dari 1 hingga sasaran, cobalah setiap koin: jika i >= coin, maka dp[i] = min(dp[i], 1 + dp[i - coin]). Jawabannya adalah dp[amount], atau -1 jika nilainya masih tak terhingga.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base case: 0 coins for amount 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:  # can use this coin
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 6, 9], 11))  # 2: (5+6)
print(coin_change([2], 3))             # -1: impossible
print(coin_change([1, 2, 5], 11))      # 3: 5+5+1
print(coin_change([186, 419, 83, 408], 6249))  # 20

Urutan Pengisian: Gagasan Penting

Urutan pengisian adalah inti DP dari bawah ke atas. Untuk keadaan dp[i] mana pun, semua keadaan yang menjadi dependensinya harus dihitung terlebih dahulu. Untuk DP 1D ketika dp[i] bergantung pada dp[i-1] dan dp[i-2], lakukan pengisian dari kiri ke kanan. Untuk DP 2D ketika dp[i][j] bergantung pada dp[i-1][j] dan dp[i][j-1], lakukan pengisian baris demi baris (dari atas ke bawah, dari kiri ke kanan). Selalu gambar panah dependensi sebelum menulis kode untuk memastikan urutan pengisiannya.

# Fill order examples:

# 1D: dp[i] = f(dp[i-1], dp[i-2])
# Arrows point LEFT: fill LEFT TO RIGHT
# i: 0 -> 1 -> 2 -> ... -> n

# 2D: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# Arrows point LEFT and UP: fill TOP-LEFT TO BOTTOM-RIGHT
# Fill row 0 first, then row 1, etc.

# 2D reversed: dp[i][j] = f(dp[i+1][j], dp[i][j+1])
# Arrows point RIGHT and DOWN: fill BOTTOM-RIGHT TO TOP-LEFT
# Used in interval DP and some string problems

print('Draw dependencies first, then determine fill order')

LCS dari Bawah ke Atas: Tabel 2D

Tabel dari bawah ke atas untuk Subsekuens Bersama Terpanjang berukuran (m+1) × (n+1), dengan dp[i][j] = LCS dari s1[:i] dan s2[:j]. Kasus dasar: dp[0][j] = dp[i][0] = 0 (untaian kosong memiliki LCS 0 dengan apa pun). Isi baris demi baris: jika s1[i-1] == s2[j-1], dp[i][j] = 1 + dp[i-1][j-1]; jika tidak, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Jawabannya adalah dp[m][n].

def lcs_bottom_up(s1, s2):
    m, n = len(s1), len(s2)
    # (m+1) x (n+1) table, initialised to 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:         # characters match
                dp[i][j] = 1 + dp[i-1][j-1]
            else:                            # skip one character
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

print(lcs_bottom_up('abcde', 'ace'))   # 3
print(lcs_bottom_up('ABCBDAB', 'BDCAB'))  # 4: 'BCAB' or 'BDAB'

Optimisasi Ruang: Larik Bergulir

Banyak tabel DP 2D dapat dikurangi menjadi 1D (atau 2 baris) dengan mengamati bahwa dp[i][j] hanya bergantung pada baris saat ini dan baris sebelumnya. Pertahankan dua larik: prev dan curr, atau perbarui satu larik dalam urutan yang tepat. Untuk LCS, dp[i][j] bergantung pada dp[i-1][j], dp[i][j-1], dan dp[i-1][j-1] — cukup dengan mempertahankan baris sebelumnya.

def lcs_space_optimised(s1, s2):
    m, n = len(s1), len(s2)
    # Keep only one row (previous row state)
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = 1 + prev[j-1]  # dp[i-1][j-1]
            else:
                curr[j] = max(prev[j], curr[j-1])  # dp[i-1][j] and dp[i][j-1]
        prev = curr
    return prev[n]

print(lcs_space_optimised('abcde', 'ace'))   # 3
# Space: O(n) instead of O(mn)

Perampokan Rumah dari Bawah ke Atas

DP dari bawah ke atas untuk perampokan rumah mengisi dp[0..n-1], dengan dp[i] = keuntungan maksimum dari merampok rumah 0 hingga i. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]), dan untuk i >= 2: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Karena dp[i] hanya bergantung pada dua nilai terakhir, ruangnya dapat langsung dioptimalkan menjadi O(1) dengan dua variabel — pola umum untuk DP 1D dengan dependensi dua langkah.

def rob_bottom_up(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]

    # Full table version: O(n) space
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    return dp[-1]

def rob_optimised(nums):
    # O(1) space: only need last two values
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
    return prev1

print(rob_optimised([2, 7, 9, 3, 1]))  # 12

Jumlah Jalur Minimum dalam Kisi

Jumlah Jalur Minimum (LeetCode #64): temukan jalur dari kiri atas ke kanan bawah yang meminimalkan jumlah nilai (Anda hanya dapat bergerak ke kanan atau ke bawah). DP 2D: dp[i][j] = jumlah minimum untuk mencapai sel (i,j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Isi dari kiri ke kanan, dari atas ke bawah. Kasus dasar: dp[0][0] = grid[0][0], baris pertama diisi hanya ke kanan, dan kolom pertama diisi hanya ke bawah.

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    # Fill first row (can only come from left)
    for c in range(1, cols):
        dp[0][c] = dp[0][c-1] + grid[0][c]
    # Fill first column (can only come from above)
    for r in range(1, rows):
        dp[r][0] = dp[r-1][0] + grid[r][0]
    # Fill rest of the table
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
    return dp[rows-1][cols-1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid))  # 7: 1+3+1+1+1

Memodifikasi Tabel DP Secara Langsung

Ketika ruang tambahan dilarang, terkadang Anda dapat memodifikasi kisi masukan itu sendiri dan menggunakannya sebagai tabel DP. Untuk jumlah jalur minimum, timpa grid[i][j] dengan biaya minimum untuk mencapai sel tersebut. Ini menggunakan ruang tambahan O(1), tetapi merusak masukan — selalu sampaikan pertukaran ini kepada pewawancara dan pastikan bahwa hal tersebut diperbolehkan. Jika masukan harus dipertahankan, gunakan pendekatan larik bergulir.

def min_path_sum_inplace(grid):
    rows, cols = len(grid), len(grid[0])
    # Modify grid in-place (O(1) extra space, destroys input)
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue  # starting cell
            elif r == 0:
                grid[r][c] += grid[r][c-1]  # first row
            elif c == 0:
                grid[r][c] += grid[r-1][c]  # first column
            else:
                grid[r][c] += min(grid[r-1][c], grid[r][c-1])
    return grid[rows-1][cols-1]

import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid)))  # 7

Membandingkan Pendekatan dari Atas ke Bawah dan dari Bawah ke Atas pada Pertukaran Koin

Kedua pendekatan menyelesaikan masalah pertukaran koin secara optimal, tetapi berbeda dalam praktiknya. Pendekatan dari atas ke bawah lebih bersih untuk ditulis dan hanya menghitung submasalah yang benar-benar dapat dijangkau. Pendekatan dari bawah ke atas menghitung semua jumlah dari 0 hingga sasaran, bahkan jumlah yang tidak dapat dicapai dengan koin yang diberikan (yang tetap bernilai tak terhingga). Untuk masalah yang jarang (sedikit keadaan yang dapat dijangkau), pendekatan dari atas ke bawah lebih efisien; untuk masalah yang padat, pendekatan dari bawah ke atas memiliki beban tambahan yang lebih rendah.

import functools

# Top-down: only computes reachable amounts
def coin_change_top(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)
    r = dp(amount)
    return r if r != float('inf') else -1

# Bottom-up: computes all amounts 0 to target
def coin_change_bottom(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i >= c: dp[i] = min(dp[i], 1 + dp[i-c])
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change_top([1,5,6,9], 11))    # 2
print(coin_change_bottom([1,5,6,9], 11)) # 2

Jalur Unik: DP 2D Klasik

Jalur Unik (LeetCode #62) menghitung jumlah jalur dari kiri atas ke kanan bawah pada kisi m×n, dengan hanya bergerak ke kanan atau ke bawah. Rekurensinya sederhana: dp[i][j] = dp[i-1][j] + dp[i][j-1] — jalur dari atas ditambah jalur dari kiri. Kasus dasar: seluruh baris pertama dan kolom pertama masing-masing memiliki tepat 1 jalur (hanya ada satu arah untuk bergerak). DP 2D ini mengisi nilai dalam O(mn) time dan dapat dikurangi menjadi ruang O(n) dengan baris bergulir.

def unique_paths(m, n):
    # dp[i][j] = number of paths to reach cell (i,j)
    dp = [[1] * n for _ in range(m)]
    # Base: first row and first column are all 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

print(unique_paths(3, 7))   # 28
print(unique_paths(3, 2))   # 3

# O(n) space rolling row:
def unique_paths_opt(m, n):
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j-1]
    return row[n-1]

print(unique_paths_opt(3, 7))  # 28

Uji Cepat

Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Rangkuman Pelajaran

Dalam pelajaran ini Anda mempelajari: DP dari bawah ke atas dengan tabulasi dan cara menentukan urutan pengisian berdasarkan panah dependensi, optimasi ruang menggunakan larik bergulir (O(mn) hingga O(n)) dan pelacakan dua variabel (O(n) hingga O(1)), serta implementasi dari bawah ke atas untuk Fibonacci, Pertukaran Koin, LCS, Perampok Rumah, dan Jumlah Jalur Minimum. Berikutnya kita menyelesaikan masalah pertukaran koin dan tangga biaya minimum secara menyeluruh.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “DP Bottom-Up dengan Tabulasi” gratis?

Ya — teks lengkap “DP Bottom-Up dengan Tabulasi” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “DP Bottom-Up dengan Tabulasi”?

Ubah solusi top-down menjadi tabel DP iteratif, lalu kurangi ruang dari O(n) menjadi O(1) ketika hanya beberapa entri terakhir yang diperlukan. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?

Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “DP Bottom-Up dengan Tabulasi” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Mengenali DP: Submasalah yang Saling Tumpang Tindih
  2. DP Top-Down dengan Memoization
  3. DP Bottom-Up dengan Tabulasi
  4. Coin Change dan Tangga Berbiaya Minimum
← Kembali ke DSA Interview Prep