07-动态规划基础

💡 核心结论

动态规划本质

  • 定义：将复杂问题分解为重叠子问题，存储子问题解避免重复计算

  • 核心：最优子结构 + 重叠子问题 = 动态规划

  • vs递归：递归重复计算，DP记忆化存储

  • vs贪心：贪心局部最优，DP考虑所有可能

  • 关键：找状态、写方程、定边界、优化空间

DP三要素（必须明确）

  1. 状态定义：dp[i]表示什么？

  2. 状态转移方程：dp[i]如何由之前的状态得到？

  3. 初始状态：dp[0]或dp[i][0]是什么？

解题步骤

  1. 暴力递归：写出递归解法

  2. 记忆化：加memo避免重复计算

  3. 自底向上：改为DP数组

  4. 空间优化：滚动数组或变量

DP vs 其他

方法

适用

时间

空间

暴力

数据小

指数级

O(1)

贪心

局部最优=全局

O(n)

O(1)

DP

重叠子问题

O(n)~O(n³)

O(n)~O(n²)

🎯 经典问题

1. 斐波那契数列

递归（指数时间）

def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
# 时间：O(2^n) 重复计算

记忆化递归

def fib(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
# 时间：O(n) 空间：O(n)

DP数组

def fib(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
# 时间：O(n) 空间：O(n)

空间优化

def fib(n):
    if n <= 1: return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr
# 时间：O(n) 空间：O(1)

2. 爬楼梯

一次爬1或2级，n级有多少种方法？

状态：dp[i] = 到第i级的方法数
转移：dp[i] = dp[i-1] + dp[i-2]
初始：dp[0]=1, dp[1]=1

def climbStairs(n):
    if n <= 1: return 1
    prev, curr = 1, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

3. 打家劫舍

不能偷相邻房屋，求最大金额

状态：dp[i] = 前i个房屋能偷的最大金额
转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
       不偷第i个     偷第i个

def rob(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    
    prev, curr = 0, 0
    for num in nums:
        prev, curr = curr, max(curr, prev + num)
    return curr

4. 最大子数组和（Kadane算法）

状态：dp[i] = 以nums[i]结尾的最大子数组和
转移：dp[i] = max(nums[i], dp[i-1] + nums[i])

def maxSubArray(nums):
    max_sum = nums[0]
    curr_sum = nums[0]
    
    for i in range(1, len(nums)):
        curr_sum = max(nums[i], curr_sum + nums[i])
        max_sum = max(max_sum, curr_sum)
    
    return max_sum

5. 最长递增子序列（LIS）

状态：dp[i] = 以nums[i]结尾的最长递增子序列长度
转移：dp[i] = max(dp[j] + 1) for j < i if nums[j] < nums[i]
时间：O(n²)

def lengthOfLIS(nums):
    if not nums: return 0
    dp = [1] * len(nums)
    
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

🎯 DP解题套路

一维DP

# 模板
dp = [0] * (n + 1)
dp[0] = initial_value

for i in range(1, n + 1):
    dp[i] = f(dp[i-1], dp[i-2], ...)

return dp[n]

二维DP

# 模板
dp = [[0] * (m + 1) for _ in range(n + 1)]

# 初始化
for i in range(n + 1):
    dp[i][0] = ...
for j in range(m + 1):
    dp[0][j] = ...

# 状态转移
for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = f(dp[i-1][j], dp[i][j-1], ...)

return dp[n][m]

📚 LeetCode练习

入门

进阶

💡 优化技巧

1. 空间优化

# 只依赖前一个状态
dp[i] = f(dp[i-1])
# 优化为一个变量

# 只依赖前两个状态
dp[i] = f(dp[i-1], dp[i-2])
# 优化为两个变量

# 只依赖上一行
dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# 优化为一维数组

2. 降维技巧

# 二维改一维
for i in range(n):
    for j in range(m):
        dp[i][j] = f(dp[i-1][j], dp[i][j-1])

# 优化为
dp = [0] * m
for i in range(n):
    for j in range(m):
        dp[j] = f(dp[j], dp[j-1])

🎯 思维导图

动态规划
├── 线性DP
│   ├── 单串：爬楼梯、打家劫舍、最大子数组
│   └── 双串：最长公共子序列、编辑距离
├── 区间DP
│   ├── 最长回文子串
│   └── 戳气球
├── 背包DP
│   ├── 0-1背包
│   ├── 完全背包
│   └── 多重背包
└── 状态机DP
    ├── 股票问题
    └── 打家劫舍II

💡 学习建议

  1. 从简单开始：斐波那契→爬楼梯→打家劫舍

  2. 画表理解：手动模拟DP过程

  3. 总结模板：相同类型问题用相同套路

  4. 优化意识：能否降维？能否滚动数组？

  5. 大量练习：至少50道DP题

学习顺序

  1. 理解递归解法

  2. 加memo优化

  3. 改为DP数组

  4. 优化空间

  5. 总结模板

💻 完整代码实现

Python 实现

  1"""
  2动态规划基础问题实现
  3"""
  4
  5# ========== 1. 斐波那契数列 ==========
  6
  7def fib_recursive(n):
  8    """递归：O(2^n)"""
  9    if n <= 1:
 10        return n
 11    return fib_recursive(n - 1) + fib_recursive(n - 2)
 12
 13
 14def fib_memo(n, memo=None):
 15    """记忆化递归：O(n)"""
 16    if memo is None:
 17        memo = {}
 18    if n in memo:
 19        return memo[n]
 20    if n <= 1:
 21        return n
 22    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
 23    return memo[n]
 24
 25
 26def fib_dp(n):
 27    """DP数组：O(n)"""
 28    if n <= 1:
 29        return n
 30    dp = [0] * (n + 1)
 31    dp[1] = 1
 32    for i in range(2, n + 1):
 33        dp[i] = dp[i - 1] + dp[i - 2]
 34    return dp[n]
 35
 36
 37def fib_optimized(n):
 38    """空间优化：O(1)"""
 39    if n <= 1:
 40        return n
 41    prev, curr = 0, 1
 42    for _ in range(2, n + 1):
 43        prev, curr = curr, prev + curr
 44    return curr
 45
 46
 47# ========== 2. 爬楼梯 ==========
 48
 49def climb_stairs(n):
 50    """一次爬1或2级，n级有多少种方法"""
 51    if n <= 1:
 52        return 1
 53    prev, curr = 1, 1
 54    for _ in range(2, n + 1):
 55        prev, curr = curr, prev + curr
 56    return curr
 57
 58
 59# ========== 3. 打家劫舍 ==========
 60
 61def rob(nums):
 62    """不能偷相邻房屋"""
 63    if not nums:
 64        return 0
 65    if len(nums) == 1:
 66        return nums[0]
 67    
 68    prev, curr = 0, 0
 69    for num in nums:
 70        prev, curr = curr, max(curr, prev + num)
 71    return curr
 72
 73
 74# ========== 4. 最大子数组和 ==========
 75
 76def max_sub_array(nums):
 77    """Kadane算法：O(n)"""
 78    max_sum = nums[0]
 79    curr_sum = nums[0]
 80    
 81    for i in range(1, len(nums)):
 82        curr_sum = max(nums[i], curr_sum + nums[i])
 83        max_sum = max(max_sum, curr_sum)
 84    
 85    return max_sum
 86
 87
 88# ========== 5. 最长递增子序列 ==========
 89
 90def length_of_lis(nums):
 91    """O(n²)解法"""
 92    if not nums:
 93        return 0
 94    
 95    dp = [1] * len(nums)
 96    
 97    for i in range(len(nums)):
 98        for j in range(i):
 99            if nums[j] < nums[i]:
100                dp[i] = max(dp[i], dp[j] + 1)
101    
102    return max(dp)
103
104
105def length_of_lis_optimized(nums):
106    """二分优化：O(n log n)"""
107    if not nums:
108        return 0
109    
110    tails = []  # tails[i]表示长度为i+1的LIS的最小末尾元素
111    
112    for num in nums:
113        # 二分查找插入位置
114        left, right = 0, len(tails)
115        while left < right:
116            mid = (left + right) // 2
117            if tails[mid] < num:
118                left = mid + 1
119            else:
120                right = mid
121        
122        if left == len(tails):
123            tails.append(num)
124        else:
125            tails[left] = num
126    
127    return len(tails)
128
129
130# ========== 6. 零钱兑换 ==========
131
132def coin_change(coins, amount):
133    """最少硬币数"""
134    dp = [float('inf')] * (amount + 1)
135    dp[0] = 0
136    
137    for i in range(1, amount + 1):
138        for coin in coins:
139            if i >= coin:
140                dp[i] = min(dp[i], dp[i - coin] + 1)
141    
142    return dp[amount] if dp[amount] != float('inf') else -1
143
144
145# ========== 7. 不同路径 ==========
146
147def unique_paths(m, n):
148    """m×n网格，从左上到右下有多少路径"""
149    dp = [[0] * n for _ in range(m)]
150    
151    # 初始化第一行和第一列
152    for i in range(m):
153        dp[i][0] = 1
154    for j in range(n):
155        dp[0][j] = 1
156    
157    # 状态转移
158    for i in range(1, m):
159        for j in range(1, n):
160            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
161    
162    return dp[m - 1][n - 1]
163
164
165def unique_paths_optimized(m, n):
166    """空间优化：O(n)"""
167    dp = [1] * n
168    
169    for i in range(1, m):
170        for j in range(1, n):
171            dp[j] += dp[j - 1]
172    
173    return dp[n - 1]
174
175
176# ========== 8. 最小路径和 ==========
177
178def min_path_sum(grid):
179    """网格中从左上到右下的最小路径和"""
180    if not grid:
181        return 0
182    
183    m, n = len(grid), len(grid[0])
184    dp = [[0] * n for _ in range(m)]
185    
186    # 初始化
187    dp[0][0] = grid[0][0]
188    for i in range(1, m):
189        dp[i][0] = dp[i - 1][0] + grid[i][0]
190    for j in range(1, n):
191        dp[0][j] = dp[0][j - 1] + grid[0][j]
192    
193    # 状态转移
194    for i in range(1, m):
195        for j in range(1, n):
196            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
197    
198    return dp[m - 1][n - 1]
199
200
201def demo():
202    """演示DP算法"""
203    print("=== 动态规划基础演示 ===\n")
204    
205    # 斐波那契
206    n = 10
207    print(f"斐波那契第{n}项:")
208    print(f"  递归: {fib_recursive(n)}")
209    print(f"  记忆化: {fib_memo(n)}")
210    print(f"  DP: {fib_dp(n)}")
211    print(f"  优化: {fib_optimized(n)}\n")
212    
213    # 爬楼梯
214    n = 5
215    print(f"爬{n}级楼梯的方法数: {climb_stairs(n)}\n")
216    
217    # 打家劫舍
218    nums = [2, 7, 9, 3, 1]
219    print(f"打家劫舍 {nums}: {rob(nums)}\n")
220    
221    # 最大子数组和
222    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
223    print(f"最大子数组和 {nums}: {max_sub_array(nums)}\n")
224    
225    # LIS
226    nums = [10, 9, 2, 5, 3, 7, 101, 18]
227    print(f"最长递增子序列 {nums}: {length_of_lis(nums)}\n")
228    
229    # 零钱兑换
230    coins, amount = [1, 2, 5], 11
231    print(f"零钱兑换 coins={coins}, amount={amount}: {coin_change(coins, amount)}\n")
232    
233    # 不同路径
234    m, n = 3, 7
235    print(f"网格 {m}×{n} 不同路径数: {unique_paths(m, n)}")
236
237
238if __name__ == '__main__':
239    demo()
240

C++ 实现

  1/**
  2 * 动态规划基础问题实现
  3 */
  4
  5#include <iostream>
  6#include <vector>
  7#include <algorithm>
  8#include <climits>
  9
 10using namespace std;
 11
 12// 斐波那契数列
 13int fib(int n) {
 14    if (n <= 1) return n;
 15    
 16    int prev = 0, curr = 1;
 17    for (int i = 2; i <= n; i++) {
 18        int temp = curr;
 19        curr = prev + curr;
 20        prev = temp;
 21    }
 22    return curr;
 23}
 24
 25// 爬楼梯
 26int climbStairs(int n) {
 27    if (n <= 1) return 1;
 28    
 29    int prev = 1, curr = 1;
 30    for (int i = 2; i <= n; i++) {
 31        int temp = curr;
 32        curr = prev + curr;
 33        prev = temp;
 34    }
 35    return curr;
 36}
 37
 38// 打家劫舍
 39int rob(const vector<int>& nums) {
 40    if (nums.empty()) return 0;
 41    if (nums.size() == 1) return nums[0];
 42    
 43    int prev = 0, curr = 0;
 44    for (int num : nums) {
 45        int temp = curr;
 46        curr = max(curr, prev + num);
 47        prev = temp;
 48    }
 49    return curr;
 50}
 51
 52// 最大子数组和
 53int maxSubArray(const vector<int>& nums) {
 54    int maxSum = nums[0];
 55    int currSum = nums[0];
 56    
 57    for (int i = 1; i < nums.size(); i++) {
 58        currSum = max(nums[i], currSum + nums[i]);
 59        maxSum = max(maxSum, currSum);
 60    }
 61    
 62    return maxSum;
 63}
 64
 65// 最长递增子序列
 66int lengthOfLIS(const vector<int>& nums) {
 67    if (nums.empty()) return 0;
 68    
 69    vector<int> dp(nums.size(), 1);
 70    
 71    for (int i = 0; i < nums.size(); i++) {
 72        for (int j = 0; j < i; j++) {
 73            if (nums[j] < nums[i]) {
 74                dp[i] = max(dp[i], dp[j] + 1);
 75            }
 76        }
 77    }
 78    
 79    return *max_element(dp.begin(), dp.end());
 80}
 81
 82// 零钱兑换
 83int coinChange(const vector<int>& coins, int amount) {
 84    vector<int> dp(amount + 1, INT_MAX);
 85    dp[0] = 0;
 86    
 87    for (int i = 1; i <= amount; i++) {
 88        for (int coin : coins) {
 89            if (i >= coin && dp[i - coin] != INT_MAX) {
 90                dp[i] = min(dp[i], dp[i - coin] + 1);
 91            }
 92        }
 93    }
 94    
 95    return dp[amount] == INT_MAX ? -1 : dp[amount];
 96}
 97
 98// 不同路径
 99int uniquePaths(int m, int n) {
100    vector<int> dp(n, 1);
101    
102    for (int i = 1; i < m; i++) {
103        for (int j = 1; j < n; j++) {
104            dp[j] += dp[j - 1];
105        }
106    }
107    
108    return dp[n - 1];
109}
110
111int main() {
112    cout << "=== 动态规划基础演示 ===" << endl << endl;
113    
114    // 斐波那契
115    int n = 10;
116    cout << "斐波那契第" << n << "项: " << fib(n) << endl << endl;
117    
118    // 爬楼梯
119    n = 5;
120    cout << "爬" << n << "级楼梯的方法数: " << climbStairs(n) << endl << endl;
121    
122    // 打家劫舍
123    vector<int> nums = {2, 7, 9, 3, 1};
124    cout << "打家劫舍 [2,7,9,3,1]: " << rob(nums) << endl << endl;
125    
126    // 最大子数组和
127    vector<int> nums2 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
128    cout << "最大子数组和: " << maxSubArray(nums2) << endl << endl;
129    
130    // LIS
131    vector<int> nums3 = {10, 9, 2, 5, 3, 7, 101, 18};
132    cout << "最长递增子序列长度: " << lengthOfLIS(nums3) << endl << endl;
133    
134    // 零钱兑换
135    vector<int> coins = {1, 2, 5};
136    int amount = 11;
137    cout << "零钱兑换 coins=[1,2,5], amount=11: " 
138         << coinChange(coins, amount) << endl << endl;
139    
140    // 不同路径
141    cout << "网格 3×7 不同路径数: " << uniquePaths(3, 7) << endl;
142    
143    return 0;
144}