Dynamic programming from entry to mastery - core ideas and classic issues

Dynamic Programming (DP) is one of the most powerful and daunting techniques in the field of algorithms. Its name sounds enigmatic—in fact, when Richard Bellman came up with the name in the 1950s, he deliberately chose a word that sounded "powerful" to win research funding. However, the core idea of ​​dynamic programming is extremely simple: decompose a complex problem into overlapping sub-problems, and avoid repeated calculations by storing the solutions to the sub-problems.

Many programmers find DP difficult for three main reasons: first, they don’t know when to use DP, second, they don’t know how to define states, and third, they don’t know how to derive state transition equations. This article will start from the core theory of DP and help you establish a complete DP thinking framework through five classic questions from shallow to deep.

Three major elements of DP

For a problem to be solved using dynamic programming, the following three conditions must be met at the same time:

1. Optimal Substructure

The optimal solution to a problem contains the optimal solutions to its subproblems. In other words, we can construct the optimal solution to the original problem by combining the optimal solutions to the subproblems. For example, in the shortest path problem, if the shortest path from A to C passes through B, then A→B and B→C are also the shortest paths respectively.

2. Overlapping Subproblems

During the recursive solution process, the same subproblem is calculated multiple times. This is exactly the advantage of DP over brute force recursion - by recording the calculated results, the exponential time complexity is reduced to the polynomial level. Taking the Fibonacci sequence as an example, when F(n) is calculated recursively, F(2) will be calculated exponential times, while DP is calculated only once.

3. No Aftereffect

Once the status of a certain stage is determined, it will not be affected by subsequent decisions. That is, future decisions will not change the past state. This requires that we must include enough information when defining the state so that the state transition only depends on the current state and decision-making, rather than the historical path.

DP four-step problem solving method

No matter how complex a DP problem is, it can be solved by following the following four steps:

**Step one: Define the state. ** Make it clear what dp[i] (or dp[i][j], etc.) means. A good state definition is the key to problem solving.

**Step 2: Derive the state transition equation. ** Find the relationship between dp[i] and dp[i-1] (or other substates). This is usually the most difficult step.

**Step 3: Determine the initial conditions (boundary conditions). ** Determine the solution to the smallest size subproblem, which is the starting point of the recursion.

**Step 4: Determine the traversal order. ** Make sure that when calculating dp[i], all its dependent substates have been calculated.

Classic Problem 1: Climbing Stairs (Getting Started)

Problem description

Suppose you are climbing a staircase with n steps, either 1 or 2 steps at a time. How many different ways are there to reach the top of the building?

Idea analysis

To reach the nth step of stairs, either climb 1 step up from the n-1th step, or climb up 2 steps from the n-2th step. Therefore the number of ways to the nth degree is equal to the sum of the number of ways to reach the n-1th and n-2th degrees.

State definition and transition equation

• State definition: dp[i] represents the number of ways to reach the i-th staircase

Code implementation

def climb_stairs(n):    if n <= 1:        return 1    dp = [0] * (n + 1)    dp[0] = 1    dp[1] = 1    for i in range(2, n + 1):        dp[i] = dp[i - 1] + dp[i - 2]    return dp[n] # 空间优化版本（只需两个变量）def climb_stairs_optimized(n):    if n <= 1:        return 1    prev2, prev1 = 1, 1    for i in range(2, n + 1):        curr = prev1 + prev2        prev2 = prev1        prev1 = curr    return prev1

复杂度分析： 时间 O(n)，空间 O(1)（优化版）。

这个问题本质上就是斐波那契数列，虽然简单，但完整展示了 DP 的四步解题法。

经典问题二：0-1 背包问题（核心）

问题描述

有 n 个物品和一个容量为 W 的背包，第 i 个物品的重量为 weight[i]，价值为 value[i]。每个物品只能选择放或不放（0-1 选择），求在不超过背包容量的前提下能获得的最大价值。

思路分析

对于每个物品，我们有两个选择：放入背包或不放入。这是一个组合优化问题，暴力枚举需要 O(2^n) 时间，而 DP 可以在 O(nW) 时间内求解。

状态定义与转移方程

• 状态定义：dp[i][j] 表示前 i 个物品中，背包容量为 j 时能获得的最大价值
• 状态转移方程：
  • 不选第 i 个物品：dp[i][j] = dp[i-1][j]
  • 选第 i 个物品（前提 j >= weight[i]）：dp[i][j] = dp[i-1][j-weight[i]] + value[i]
  • 取两者最大值：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
• 初始条件：dp[0][j] = 0（没有物品可选，价值为 0）

代码实现

def knapsack_01(weights, values, capacity):    n = len(weights)    # dp[i][j]: 前i个物品、容量j时的最大价值    dp = [[0] * (capacity + 1) for _ in range(n + 1)]     for i in range(1, n + 1):     return dp[n][capacity] # Space optimization: one-dimensional array (traversal in reverse order ensures that each item is only selected once)     for i in range(n):     return dp[capacity] **Complexity analysis:** Time O(nW), space O(W) (optimized version). Note that the inner loop in the one-dimensional optimized version must be traversed in reverse order because we need to use the value of the "previous row". If traversed in forward order, `dp[j - weights[i]]` may have been updated by the current row, which is equivalent to the item being selected repeatedly (this becomes a complete knapsack problem). ## Classic Problem 3: Longest Common Subsequence LCS ### Problem description Given two strings s1 and s2, find the length of their longest common subsequence. The subsequences are not required to be consecutive, but are required to maintain the original order. ### Idea analysis Compare the characters at the current positions of the two strings: if they are the same, add 1 to the LCS length; if they are different, try to skip the current characters of one string respectively and take the larger value. ### State definition and transition equation - State definition: `dp[i][j]` represents the LCS length of the first i characters of s1 and the first j characters of s2 ### Code implementation ```pythondef longest_common_subsequence(s1, s2):    m, n = len(s1), len(s2)    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]:                dp[i][j] = dp[i - 1][j - 1] + 1            else:                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])     return dp[m][n] # 示例print(longest_common_subsequence("abcde", "ace"))  # 输出: 3 ("ace")

复杂度分析： 时间 O(mn)，空间 O(mn)，可优化至 O(min(m,n))。

经典问题四：编辑距离（Levenshtein Distance）

问题描述

给定两个字符串 word1 和 word2，求将 word1 转换为 word2 所需的最少操作数。允许的操作有：插入一个字符、删除一个字符、替换一个字符。

思路分析

编辑距离是自然语言处理、拼写检查、DNA 序列比对等领域的基础算法。我们可以定义一个二维 DP 表，其中每个单元格表示两个字符串前缀之间的编辑距离。

状态定义与转移方程

• 状态定义：dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数
• 状态转移方程：
  • 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]（无需操作）
  • 否则：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
    • dp[i-1][j] + 1：删除 word1 的第 i 个字符
    • dp[i][j-1] + 1：在 word1 中插入 word2 的第 j 个字符
    • dp[i-1][j-1] + 1：替换 word1 的第 i 个字符
• 初始条件：dp[i][0] = i，dp[0][j] = j

代码实现

def edit_distance(word1, word2):    m, n = len(word1), len(word2)    dp = [[0] * (n + 1) for _ in range(m + 1)]     #Initial conditions     # Fill in the form     return dp[m][n] # Example **Complexity analysis:** Time O(mn), space O(mn), rolling array can be used to optimize to O(min(m,n)). ## Classic Problem 5: Longest Increasing Subsequence LIS ### Problem description Given an array of integers, find the length of the longest strictly increasing subsequence in it. ### Idea analysis There are many solutions to the LIS problem, ranging from O(n²) basic DP to O(n log n) greedy+bisection optimization. ### State definition and transition equation **Method 1: O(n²) DP**- State definition: `dp[i]` represents the length of the longest increasing subsequence ending with `nums[i]`- State transition equation: `dp[i] = max(dp[j] + 1)` where `0 <= j < i` and `nums[j] < nums[i]`- Initial condition: `dp[i] = 1` (each element itself constitutes a subsequence of length 1) ### Code implementation ```python# 方法一：O(n²) DPdef length_of_lis(nums):    if not nums:        return 0    n = len(nums)    dp = [1] * n     for i in range(1, n):        for j in range(i):            if nums[j] < nums[i]:                dp[i] = max(dp[i], dp[j] + 1)     return max(dp) # 方法二：O(n log n) 贪心 + 二分查找import bisect def length_of_lis_optimized(nums):    # tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素    tails = []    for num in nums:        pos = bisect.bisect_left(tails, num)        if pos == len(tails):            tails.append(num)        else:            tails[pos] = num    return len(tails) # 示例print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 输出: 4 ([2,3,7,101])

复杂度分析： 方法一时间 O(n²)，空间 O(n)；方法二时间 O(n log n)，空间 O(n)。

方法二的核心思想是贪心：为了让递增子序列尽可能长，我们希望每个位置的末尾元素尽可能小。tails 数组始终保持有序，因此可以用二分查找高效定位插入位置。

DP 优化技巧

滚动数组

当状态转移只涉及相邻两行时（如 dp[i] 只依赖 dp[i-1]），可以用两个一维数组交替使用，将空间从 O(mn) 降至 O(n)：

# 以 LCS 为例的滚动数组优化def lcs_rolling(s1, s2):    m, n = len(s1), len(s2)    prev = [0] * (n + 1)    curr = [0] * (n + 1)     for i in range(1, m + 1):     return prev[n] ### One-dimensional space compression We've seen in the 0-1 knapsack that we can update in-place on a one-dimensional array by traversing in reverse order, avoiding the use of a two-dimensional array. The key to this technique is understanding the impact of traversal order on dependencies. ## Memoized search vs bottom-up DP has two implementation methods: | Features | Memoized search (top-down) | Table method (bottom-up) ||-----|--------------------------|------------------|| Implementation method | Recursion + hash table/array cache | Iteration + array filling || Way of thinking | Natural recursive thinking, more intuitive | Need to think clearly about the traversal order || Calculation amount | Calculate only required subproblems | Calculate all subproblems || Space overhead | Recursive stack + cache | Arrays only || Constant factor | Recursive call overhead is large | Loop overhead is small || Applicable scenarios | The state space is sparse and complex | The state space is dense and regular | ```python# 记忆化搜索示例（爬楼梯）from functools import lru_cache @lru_cache(maxsize=None)def climb_memo(n):    if n <= 1:        return 1    return climb_memo(n - 1) + climb_memo(n - 2)

对于大多数竞赛题目和实际应用，自底向上的表格法更常用，因为没有递归栈溢出的风险且常数因子更小。而记忆化搜索在状态空间不规则或状态定义复杂时更具优势。

何时使用动态规划

判断一个问题是否适合 DP，可以从以下角度思考：

1. 问题是否要求最优值（最大/最小/最长/最短/方案数）？如果是，可能适合 DP。
2. 问题是否具有选择性（选或不选、走左还是走右）？如果每一步都有选择，可能适合 DP。
3. 暴力解法是否有大量重复计算？画出递归树，观察是否存在重复子问题。
4. 能否定义清晰的状态？如果一个子问题的解可以用有限个参数唯一确定，就可以用 DP。
5. 贪心是否可行？如果局部最优不能导出全局最优，而 DP 可以通过枚举所有选择来保证全局最优。

常见的 DP 问题类型包括：线性 DP（爬楼梯、LIS）、区间 DP（矩阵链乘法、戳气球）、背包 DP（0-1 背包、完全背包）、树形 DP（二叉树中的最大路径和）、状态压缩 DP（旅行商问题）、数位 DP（统计满足条件的数字个数）等。

总结

动态规划的精髓在于用空间换时间，通过存储子问题的解来避免重复计算。掌握 DP 需要大量练习，但核心方法论是统一的：

1. 想清楚状态是什么——这是 DP 最关键的一步
2. 推导状态转移方程——从最后一步反推
3. 明确初始条件和遍历顺序
4. 考虑空间优化的可能性

从爬楼梯到背包问题，从 LCS 到编辑距离，每一个经典问题都是一种思维模式的训练。当你做够了足够多的题目，你会发现新问题往往是经典模型的变形或组合。动态规划不是天赋，而是可以通过系统训练习得的技能。