DP Bawah ke Atas dengan Penjadualan
Tukarkan penyelesaian atas ke bawah kepada jadual DP lelaran, serta kurangkan ruang daripada O(n) kepada O(1) apabila hanya beberapa entri terakhir diperlukan.
DP Bawah ke Atas dengan Penjadualan ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 3 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.
DP Bawah ke Atas: Pendekatan Tabulasi
DP bawah ke atas (tabulasi) mengisi jadual jawapan submasalah bermula daripada submasalah terkecil dan membinanya sehingga mencapai jawapan. Daripada melakukan rekursi ke bawah dan menyimpan hasil ketika kembali ke atas, anda mengira secara beriterasi dari asas. Jadual itu biasanya berupa tatasusunan 1D atau 2D yang setiap selnya dikira berdasarkan sel yang telah diisi sebelumnya. Ini menghapuskan rekursi sepenuhnya — tiada tindanan panggilan, tiada had rekursi dan lokaliti tembolok 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 Bawah ke Atas
Fibonacci bawah ke atas mengisi dp[0..n] dari kiri ke kanan. dp[i] = dp[i-1] + dp[i-2] untuk i >= 2. Kes asas ialah dp[0] = 0 dan dp[1] = 1, yang disimpan terus dalam tatasusunan. Masanya ialah O(n) dan ruangnya ialah O(n) untuk jadual penuh. Setelah anda melihat bahawa dp[i] hanya bergantung pada dua nilai terakhir, anda boleh mengurangkan ruang kepada O(1) dengan dua pemboleh ubah — inilah langkah pengoptimuman 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)) # 12586269025Pertukaran Syiling Bawah ke Atas
Bagi pertukaran syiling, jadual bawah ke atas ialah dp[0..amount], dengan dp[i] = bilangan minimum syiling untuk membentuk amaun i. Mulakan dp[0] = 0 (sifar syiling untuk amaun sifar) dan dp[1..amount] = infiniti. Bagi setiap amaun i dari 1 hingga sasaran, cuba setiap syiling: jika i >= coin, maka dp[i] = min(dp[i], 1 + dp[i - coin]). Jawapannya ialah dp[amount], atau -1 jika nilainya masih infiniti.
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)) # 20Urutan Pengisian: Pandangan Kritikal
Urutan pengisian ialah inti pati DP bawah ke atas. Bagi sebarang keadaan dp[i], semua keadaan yang menjadi kebergantungannya mesti dikira terlebih dahulu. Bagi DP 1D yang dp[i]-nya bergantung pada dp[i-1] dan dp[i-2], isi dari kiri ke kanan. Bagi DP 2D yang dp[i][j]-nya bergantung pada dp[i-1][j] dan dp[i][j-1], isi baris demi baris (dari atas ke bawah, dari kiri ke kanan). Sentiasa lukis anak panah kebergantungan sebelum menulis kod untuk mengesahkan urutan pengisian.
# 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 Bawah ke Atas: Jadual 2D
Jadual bawah ke atas bagi Subjujukan Sepunya Terpanjang berukuran (m+1) × (n+1), dengan dp[i][j] = LCS bagi s1[:i] dan s2[:j]. Kes asas: dp[0][j] = dp[i][0] = 0 (rentetan kosong mempunyai LCS 0 dengan apa-apa rentetan). 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]). Jawapannya ialah 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'Pengoptimuman Ruang: Tatasusunan Bergilir
Banyak jadual DP 2D boleh dikurangkan kepada 1D (atau 2 baris) dengan memerhatikan bahawa dp[i][j] hanya bergantung pada baris semasa dan baris sebelumnya. Simpan dua tatasusunan: prev dan curr, atau kemas kini satu tatasusunan mengikut urutan yang betul. Bagi LCS, dp[i][j] bergantung pada dp[i-1][j], dp[i][j-1] dan dp[i-1][j-1] — menyimpan baris sebelumnya sahaja sudah memadai.
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)Perompak Rumah Bawah ke Atas
Perompak rumah bawah ke atas mengisi dp[0..n-1], dengan dp[i] = keuntungan maksimum daripada merompak 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]). Oleh sebab dp[i] hanya bergantung pada dua nilai terakhir, ruangnya boleh dioptimumkan serta-merta kepada O(1) dengan dua pemboleh ubah — pola lazim bagi DP 1D dengan kebergantungan 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])) # 12Jumlah Laluan Minimum dalam Kisi
Jumlah Laluan Minimum (LeetCode #64): cari laluan dari kiri atas ke kanan bawah yang meminimumkan jumlah nilai (anda hanya boleh 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. Kes asas: dp[0][0] = grid[0][0], baris pertama diisi dengan pergerakan ke kanan sahaja, dan lajur pertama diisi dengan pergerakan ke bawah sahaja.
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+1Mengubah Jadual DP di Tempat
Apabila ruang tambahan dilarang, kadangkala anda boleh mengubah grid masukan itu sendiri untuk dijadikan jadual DP. Bagi jumlah laluan minimum, tulis ganti grid[i][j] dengan kos minimum untuk mencapai sel tersebut. Ini menggunakan ruang tambahan O(1), tetapi memusnahkan masukan — sentiasa nyatakan pertukaran ini kepada penemuduga dan sahkan bahawa ia boleh diterima. Jika masukan mesti dikekalkan, gunakan pendekatan tatasusunan bergilir.
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))) # 7Membandingkan Pendekatan Atas-ke-Bawah dan Bawah-ke-Atas dalam Pertukaran Syiling
Kedua-dua pendekatan menyelesaikan masalah pertukaran syiling secara optimum, tetapi berbeza dalam amalan. Pendekatan atas-ke-bawah lebih mudah ditulis dan hanya mengira submasalah yang benar-benar boleh dicapai. Pendekatan bawah-ke-atas mengira semua amaun dari 0 hingga sasaran, termasuk amaun yang tidak boleh dicapai dengan syiling yang diberikan (yang kekal pada nilai infiniti). Bagi masalah jarang (sedikit keadaan yang boleh dicapai), pendekatan atas-ke-bawah lebih cekap; bagi masalah padat, pendekatan bawah-ke-atas mempunyai 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)) # 2Laluan Unik: DP 2D Klasik
Laluan Unik (LeetCode #62) mengira bilangan laluan dari penjuru kiri atas ke penjuru kanan bawah grid m×n, dengan pergerakan hanya ke kanan atau ke bawah. Rumus rekursinya mudah: dp[i][j] = dp[i-1][j] + dp[i][j-1] — laluan dari atas ditambah laluan dari kiri. Kes asasnya: seluruh baris pertama dan lajur pertama masing-masing mempunyai tepat 1 laluan (hanya satu arah untuk bergerak). DP 2D ini mengisi jadual dalam masa O(mn) dan boleh dikurangkan kepada 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)) # 28Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ulang Kaji Pelajaran
Dalam pelajaran ini, anda telah mempelajari: DP bawah-ke-atas dengan pengisian jadual serta cara menentukan susunan pengisian berdasarkan anak panah kebergantungan, pengoptimuman ruang menggunakan tatasusunan bergulir (O(mn) kepada O(n)) dan penjejakan dengan dua pemboleh ubah (O(n) kepada O(1)), serta pelaksanaan bawah-ke-atas bagi Fibonacci, pertukaran syiling, LCS, perompak rumah dan jumlah laluan minimum. Seterusnya, kita akan menyelesaikan masalah pertukaran syiling dan tangga kos minimum dari awal hingga akhir.
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
Soalan Lazim
Adakah pelajaran “DP Bawah ke Atas dengan Penjadualan” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “DP Bawah ke Atas dengan Penjadualan”, 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 “DP Bawah ke Atas dengan Penjadualan”?
Tukarkan penyelesaian atas ke bawah kepada jadual DP lelaran, serta kurangkan ruang daripada O(n) kepada O(1) apabila hanya beberapa entri terakhir diperlukan. 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 3 daripada 4.
Berapa lamakah pelajaran “DP Bawah ke Atas dengan Penjadualan” 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
- Mengenal Pasti DP: Submasalah Bertindih
- DP Atas ke Bawah dengan Memoisasi
- DP Bawah ke Atas dengan Penjadualan
- Perubahan Syiling dan Tangga Kos Minimum