自底向上的 DP 与制表法
将自顶向下的解法转换为迭代 DP 表；当只需保留最近几项时，将空间从 O(n) 降至 O(1)。
自底向上的 DP 与制表法 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
自底向上 DP：填表法
自底向上 DP（填表法）从最小的子问题开始填写子问题答案表，逐步构建出最终答案。它不是向下递归并在返回过程中缓存，而是从基础开始迭代计算。该表通常是一维或二维数组，每个单元格都根据之前已经填写的单元格计算得出。这会彻底消除递归——没有调用栈、没有递归限制，并且缓存局部性更好。
# 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')自底向上计算斐波那契
自底向上的斐波那契算法从左到右填写 dp[0..n]。对于 i >= 2，dp[i] = dp[i-1] + dp[i-2]。基本情况是 dp[0] = 0 和 dp[1] = 1，直接存储在数组中。完整表的时间复杂度为 O(n)，空间复杂度为 O(n)。一旦发现 dp[i] 只依赖最后两个值，就可以用两个变量将空间降至 O(1)——这就是空间优化步骤。
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自底向上解决零钱兑换
对于零钱兑换，自底向上的表是 dp[0..amount]，其中 dp[i] 表示凑出金额 i 所需的最少硬币数。初始化 dp[0] = 0（金额为零时需要零枚硬币），并将 dp[1..amount] 初始化为无穷大。对于从 1 到目标金额的每个金额 i，尝试每枚硬币：如果 i >= coin，则 dp[i] = min(dp[i], 1 + dp[i - coin])。答案是 dp[amount]；如果仍为无穷大，则返回 -1。
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填表顺序：关键洞察
填表顺序是自底向上 DP 的核心。对于任意状态 dp[i]，它所依赖的所有状态都必须先计算。对于 dp[i] 依赖 dp[i-1] 和 dp[i-2] 的一维 DP，应从左到右填表。对于 dp[i][j] 依赖 dp[i-1][j] 和 dp[i][j-1] 的二维 DP，应逐行填表（从上到下、从左到右）。编写代码前，请始终画出依赖箭头，以确认填表顺序。
# 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：二维表
最长公共子序列的自底向上表格大小为 (m+1) × (n+1)，其中 dp[i][j] = s1[:i] 和 s2[:j] 的 LCS。如果为空字符串，基本情况为 dp[0][j] = dp[i][0] = 0（空字符串与任何内容的 LCS 都为 0）。逐行填表：如果 s1[i-1] == s2[j-1]，则 dp[i][j] = 1 + dp[i-1][j-1]；否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。答案是 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'空间优化：滚动数组
通过观察 dp[i][j] 只依赖当前行和上一行，许多二维 DP 表都可以缩减为一维（或两行）。您可以保留两个数组：prev 和 curr，或者按照正确的顺序更新单个数组。对于 LCS，dp[i][j] 依赖 dp[i-1][j]、dp[i][j-1] 和 dp[i-1][j-1]——只保留上一行就足够了。
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)自底向上解决打家劫舍
打家劫舍的自底向上算法填写 dp[0..n-1]，其中 dp[i] 表示抢劫 0 到 i 号房屋可获得的最大金额。dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])，对于 i >= 2：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。由于 dp[i] 只依赖最后两个值，因此可以立即使用两个变量将空间优化到 O(1)——这是具有两步依赖关系的一维 DP 中的常见模式。
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网格中的最小路径和
最小路径和（LeetCode #64）：找到一条从左上角到右下角的路径，使数值之和最小（只能向右或向下移动）。二维 DP：dp[i][j] = 到达单元格 (i,j) 的最小和。dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。从左到右、从上到下填表。基本情况是：dp[0][0] = grid[0][0]，第一行只能向右填充，第一列只能向下填充。
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原地修改 DP 表
当禁止使用额外空间时，有时可以直接修改输入网格，将其作为 DP 表。对于最小路径和，用到达该单元格的最小代价覆盖 grid[i][j]。这样只需 O(1) 的额外空间，但会破坏输入——请始终向面试官说明这一权衡，并确认可以接受。如果必须保留输入，请改用滚动数组方法。
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比较硬币兑换问题中的自顶向下与自底向上方法
两种方法都能求出硬币兑换问题的最优解，但在实际使用中有所不同。自顶向下方法更易于编写，而且只计算实际可达的子问题。自底向上方法会计算从 0 到目标值的所有金额，即使给定硬币无法凑出其中某些金额（这些金额会保持为无穷大）。对于稀疏问题（可达状态较少），自顶向下方法更高效；对于稠密问题，自底向上方法的额外开销更低。
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不同路径：经典二维 DP
不同路径（LeetCode #62）要求计算在一个 m×n 网格中，从左上角移动到右下角的路径数量，移动方向只能是向右或向下。递推关系很直接：dp[i][j] = dp[i-1][j] + dp[i][j-1]——来自上方的路径数加上来自左方的路径数。基础情况是：第一行和第一列都各有且只有 1 条路径（因为只有一个方向可以移动）。这种二维 DP 可在 O(mn) time 内完成，并借助滚动行将空间复杂度降至 O(n)。
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快速检查
请测试您对本课程中数据结构 & 算法——编程面试准备相关概念的理解。
课程回顾
本课中您学习了：使用制表法的自底向上 DP，以及如何根据依赖箭头确定填充顺序；使用滚动数组进行空间优化（从 O(mn) 降至 O(n)），以及使用两个变量进行跟踪（从 O(n) 降至 O(1)）；还学习了斐波那契数列、硬币兑换、LCS、打家劫舍和最小路径和的自底向上实现。接下来，我们将完整解决硬币兑换和最小代价爬楼梯问题。
常见问题解答
「自底向上的 DP 与制表法」课时是免费的吗？
是的 — 「自底向上的 DP 与制表法」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「自底向上的 DP 与制表法」这节课中我会学到什么？
将自顶向下的解法转换为迭代 DP 表；当只需保留最近几项时，将空间从 O(n) 降至 O(1)。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「自底向上的 DP 与制表法」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 识别 DP：重叠子问题
- 自顶向下的 DP 与记忆化
- 自底向上的 DP 与制表法
- 零钱兑换与最低成本爬楼梯