Bottom-Up-DP mit Tabellierung
Wandeln Sie Top-Down-Lösungen in iterative DP-Tabellen um und reduzieren Sie den Speicher von O(n) auf O(1), wenn nur die letzten Einträge benötigt werden.
Bottom-Up-DP mit Tabellierung ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Bottom-up-DP: Der Tabellierungsansatz
Bottom-up-DP (Tabellierung) füllt eine Tabelle mit den Antworten der Teilprobleme, beginnend bei den kleinsten Teilproblemen und aufbauend bis zur Lösung. Statt rekursiv nach unten zu gehen und die Ergebnisse auf dem Rückweg zu speichern, berechnen Sie die Werte iterativ von Grund auf. Die Tabelle ist typischerweise ein eindimensionales oder zweidimensionales Array, in dem jede Zelle aus bereits gefüllten Zellen berechnet wird. Dadurch entfällt die Rekursion vollständig — kein Aufruf-Stack, kein Rekursionslimit und eine bessere Cache-Lokalität.
# 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')Bottom-up-Fibonacci
Beim Bottom-up-Fibonacci wird dp[0..n] von links nach rechts gefüllt. Für i >= 2 gilt dp[i] = dp[i-1] + dp[i-2]. Die Basisfälle dp[0] = 0 und dp[1] = 1 werden direkt im Array gespeichert. Die Laufzeit beträgt O(n), der Speicherbedarf für die vollständige Tabelle O(n). Sobald Sie erkennen, dass dp[i] nur von den beiden letzten Werten abhängt, können Sie den Speicherbedarf mit zwei Variablen auf O(1) reduzieren — das ist der Schritt der Speicheroptimierung.
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)) # 12586269025Bottom-up-Coin-Change
Bei Coin Change reicht die Bottom-up-Tabelle von dp[0..amount], wobei dp[i] die minimale Anzahl an Münzen für den Betrag i angibt. Initialisieren Sie dp[0] = 0 (null Münzen für den Betrag null) und dp[1..amount] = unendlich. Probieren Sie für jeden Betrag i von 1 bis zum Zielbetrag jede Münze aus: Falls i >= coin gilt, setzen Sie dp[i] = min(dp[i], 1 + dp[i - coin]). Die Antwort ist dp[amount] oder -1, falls der Wert weiterhin unendlich ist.
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)) # 20Füllreihenfolge: Die entscheidende Erkenntnis
Die Füllreihenfolge ist das Herzstück von Bottom-up-DP. Für jeden Zustand dp[i] müssen alle Zustände, von denen er abhängt, zuvor berechnet worden sein. Bei einer eindimensionalen DP, in der dp[i] von dp[i-1] und dp[i-2] abhängt, füllen Sie die Tabelle von links nach rechts. Bei einer zweidimensionalen DP, in der dp[i][j] von dp[i-1][j] und dp[i][j-1] abhängt, füllen Sie sie zeilenweise (von oben nach unten und innerhalb jeder Zeile von links nach rechts). Zeichnen Sie vor dem Programmieren immer die Abhängigkeitspfeile ein, um die Füllreihenfolge zu bestätigen.
# 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')Bottom-up-LCS: Zweidimensionale Tabelle
Die Bottom-up-Tabelle für die Longest Common Subsequence hat die Größe (m+1) × (n+1), wobei dp[i][j] die LCS von s1[:i] und s2[:j] angibt. Basisfälle: dp[0][j] = dp[i][0] = 0 (der leere String hat mit jedem anderen String eine LCS der Länge 0). Füllen Sie die Tabelle zeilenweise: Falls s1[i-1] == s2[j-1] gilt, ist dp[i][j] = 1 + dp[i-1][j-1]; andernfalls ist dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Die Antwort ist 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'Speicheroptimierung: Rollendes Array
Viele zweidimensionale DP-Tabellen lassen sich auf eine Dimension (oder zwei Zeilen) reduzieren, indem man erkennt, dass dp[i][j] nur von der aktuellen und der vorherigen Zeile abhängt. Verwenden Sie zwei Arrays: prev und curr, oder aktualisieren Sie ein einzelnes Array in der richtigen Reihenfolge. Bei LCS hängt dp[i][j] von dp[i-1][j], dp[i][j-1] und dp[i-1][j-1] ab — dafür genügt es, nur die vorherige Zeile beizubehalten.
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)Bottom-up-House-Robber
Bei House Robber wird bottom-up dp[0..n-1] gefüllt, wobei dp[i] den maximalen Gewinn beim Ausrauben der Häuser 0 bis i angibt. Es gilt dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) und für i >= 2: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Da dp[i] nur von den beiden letzten Werten abhängt, lässt sich der Speicherbedarf unmittelbar mit zwei Variablen auf O(1) optimieren — ein häufiges Muster bei eindimensionaler DP mit Abhängigkeiten über zwei Schritte.
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])) # 12Minimale Pfadsumme in einem Gitter
Minimum Path Sum (LeetCode #64): Finden Sie einen Pfad von oben links nach unten rechts, für den die Summe der Werte minimal ist (Sie dürfen sich nur nach rechts oder unten bewegen). Zweidimensionale DP: dp[i][j] = minimale Summe, um die Zelle (i,j) zu erreichen. Es gilt dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Füllen Sie die Tabelle von links nach rechts und von oben nach unten. Basisfall: dp[0][0] = grid[0][0]; die erste Zeile wird ausschließlich nach rechts und die erste Spalte ausschließlich nach unten gefüllt.
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+1Die DP-Tabelle direkt in der Eingabe verändern
Wenn zusätzlicher Speicher nicht erlaubt ist, können Sie manchmal das Eingabegitter selbst als DP-Tabelle verwenden. Überschreiben Sie für die minimale Pfadsumme grid[i][j] mit den minimalen Kosten, um diese Zelle zu erreichen. Dadurch wird zusätzlicher Speicher von O(1) verwendet, aber die Eingabe zerstört — weisen Sie die interviewende Person immer auf diesen Kompromiss hin und bestätigen Sie, dass er akzeptabel ist. Wenn die Eingabe erhalten bleiben muss, verwenden Sie stattdessen den Ansatz mit dem rollenden Array.
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))) # 7Top-down und Bottom-up bei Coin Change vergleichen
Beide Ansätze lösen Coin Change optimal, unterscheiden sich aber in der Praxis. Top-down lässt sich übersichtlicher schreiben und berechnet nur Teilprobleme, die tatsächlich erreichbar sind. Bottom-up berechnet alle Beträge von 0 bis zum Zielbetrag, auch solche, die mit den gegebenen Münzen nicht erreichbar sind und daher auf Unendlich bleiben. Bei dünn besetzten Problemen mit wenigen erreichbaren Zuständen ist Top-down effizienter; bei dicht besetzten Problemen hat Bottom-up einen geringeren Overhead.
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)) # 2Unique Paths: Klassische 2D-DP
Unique Paths (LeetCode #62) zählt die Anzahl der Wege von der linken oberen zur rechten unteren Ecke eines m×n-Rasters, wobei man sich nur nach rechts oder unten bewegen darf. Die Rekurrenz ist direkt: dp[i][j] = dp[i-1][j] + dp[i][j-1] — Wege von oben plus Wege von links. Als Basisfälle haben die gesamte erste Zeile und die gesamte erste Spalte jeweils genau 1 Weg, da man sich nur in eine Richtung bewegen kann. Diese 2D-DP wird in O(mn) Zeit ausgefüllt und lässt sich mit einer rollierenden Zeile auf O(n) Speicher reduzieren.
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)) # 28Schnelltest
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie Bottom-up-DP mit Tabellierung und das Bestimmen der Füllreihenfolge anhand von Abhängigkeitspfeilen gelernt, außerdem die Speicheroptimierung mit rollierenden Arrays (von O(mn) auf O(n)) und mit zwei verfolgten Variablen (von O(n) auf O(1)) sowie Bottom-up-Implementierungen für Fibonacci, Coin Change, LCS, House Robber und Minimum Path Sum. Als Nächstes lösen wir die Probleme Coin Change und Min-Cost Staircase vollständig von Anfang bis Ende.
Häufig gestellte Fragen
Ist die Lektion „Bottom-Up-DP mit Tabellierung“ kostenlos?
Ja — der vollständige Text von „Bottom-Up-DP mit Tabellierung“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Bottom-Up-DP mit Tabellierung“?
Wandeln Sie Top-Down-Lösungen in iterative DP-Tabellen um und reduzieren Sie den Speicher von O(n) auf O(1), wenn nur die letzten Einträge benötigt werden. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Bottom-Up-DP mit Tabellierung“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- DP erkennen: Überlappende Teilprobleme
- Top-Down-DP mit Memoisation
- Bottom-Up-DP mit Tabellierung
- Coin Change und Treppe mit minimalen Kosten