一维动态规划：化繁为简的智慧

记住过去，才能更好地面对未来

什么是动态规划

动态规划（Dynamic Programming，DP）是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。

核心思想：将一个问题拆分成若干子问题，保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

形象理解

想象你在爬楼梯：

1
2
3
4
5
6
7
8
9
到第10层有多少种走法？

暴力：枚举所有可能的走法（指数级复杂度）

动态规划：
- 到第10层 = 从第9层走1步 + 从第8层走2步
- 到第9层 = 从第8层走1步 + 从第7层走2步
- ...
只需要记住前面的结果！

DP的核心要素

三大特征

graph LR
    A[动态规划] --> B[最优子结构]
    A --> C[重叠子问题]
    A --> D[无后效性]
    
    B --> B1[最优解包含子问题最优解]
    C --> C1[子问题会重复出现]
    D --> D1[当前状态不受未来影响]
    
    style A fill:#FFE4B5
    style B fill:#90EE90
    style C fill:#87CEEB

四个步骤

  1. 定义状态：dp[i] 表示什么含义
  2. 状态转移方程：dp[i] 如何从之前的状态推导
  3. 初始化：边界条件
  4. 计算顺序：从小到大还是从大到小

经典问题详解

1. 爬楼梯（LeetCode 70）

假设你正在爬楼梯，需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶？

问题分析

1
2
3
4
5
6
7
n = 3

方法1: 1步 + 1步 + 1步
方法2: 1步 + 2步
方法3: 2步 + 1步

共3种方法

DP思路

1
2
3
4
5
到达第 n 阶的方法数 = 到达第 n-1 阶的方法数 + 到达第 n-2 阶的方法数

为什么？
- 从第 n-1 阶走1步到达第 n 阶
- 从第 n-2 阶走2步到达第 n 阶

状态定义

1
dp[i]：到达第 i 阶的方法数

状态转移方程

1
dp[i] = dp[i-1] + dp[i-2]

这不就是斐波那契数列吗！

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 方法1：DP数组
int climbStairs(int n) {
    if (n <= 2) return n;
    
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}

// 方法2：空间优化（滚动变量）
int climbStairs(int n) {
    if (n <= 2) return n;
    
    int prev2 = 1, prev1 = 2;
    
    for (int i = 3; i <= n; ++i) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

时间复杂度：O(n)
空间复杂度：O(n) → 优化后 O(1)

执行过程

1
2
3
4
5
6
7
n = 5

i=3: dp[3] = dp[2] + dp[1] = 2 + 1 = 3
i=4: dp[4] = dp[3] + dp[2] = 3 + 2 = 5
i=5: dp[5] = dp[4] + dp[3] = 5 + 3 = 8

答案：8种方法

2. 打家劫舍（LeetCode 198）

你是一个专业的小偷，沿着一条街有若干房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

问题分析

1
2
3
4
5
输入：[2,7,9,3,1]
输出：12
解释：偷窃1号房屋(2)，3号房屋(9)，5号房屋(1) = 2 + 9 + 1 = 12

不能偷相邻的房屋！

DP思路

对于第 i 间房屋，有两个选择：

1
2
3
4
1. 偷第 i 间：获得 nums[i] + dp[i-2]（不能偷第 i-1 间）
2. 不偷第 i 间：保持 dp[i-1]

选最大的！

状态定义

1
dp[i]：考虑前 i 间房屋，能偷到的最大金额

状态转移方程

1
2
3
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
         ↑           ↑
       不偷第i间    偷第i间

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 方法1：DP数组
int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    
    vector<int> dp(n);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    
    for (int i = 2; i < n; ++i) {
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    }
    
    return dp[n-1];
}

// 方法2：空间优化
int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    
    int prev2 = nums[0];
    int prev1 = max(nums[0], nums[1]);
    
    for (int i = 2; i < n; ++i) {
        int current = max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

执行过程

1
2
3
4
5
6
7
8
9
nums = [2, 7, 9, 3, 1]

i=0: dp[0] = 2
i=1: dp[1] = max(2, 7) = 7
i=2: dp[2] = max(7, 2+9) = 11
i=3: dp[3] = max(11, 7+3) = 11
i=4: dp[4] = max(11, 11+1) = 12

答案：12

可视化决策：

1
2
3
4
5
房屋：  [2]  [7]  [9]  [3]  [1]
决策：   √    √    √    ✗    √
       偷   偷   偷   不偷  偷

2 + 9 + 1 = 12（不能偷7和3，因为相邻）

3. 最大子数组和（LeetCode 53）- Kadane算法

给定一个整数数组，找到具有最大和的连续子数组。

状态定义

1
dp[i]：以第 i 个元素结尾的最大子数组和

状态转移方程

1
2
3
dp[i] = max(nums[i], dp[i-1] + nums[i])
         ↑            ↑
      重新开始      继续累加

代码实现

1
2
3
4
5
6
7
8
9
10
11
int maxSubArray(vector<int>& nums) {
    int maxEndingHere = nums[0];
    int maxSoFar = nums[0];
    
    for (int i = 1; i < nums.size(); ++i) {
        maxEndingHere = max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

详见之前的 Kadane算法博客

4. 买卖股票的最佳时机（LeetCode 121）

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。你只能选择某一天买入并在未来某一天卖出，计算你所能获取的最大利润。

问题分析

1
2
3
输入：[7,1,5,3,6,4]
输出：5
解释：第2天买入(1)，第5天卖出(6)，利润 = 6-1 = 5

方法1：保存最低价格

1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;
    
    for (int price : prices) {
        minPrice = min(minPrice, price);
        maxProfit = max(maxProfit, price - minPrice);
    }
    
    return maxProfit;
}

方法2：DP视角

1
dp[i]：第 i 天卖出能获得的最大利润
1
2
3
4
5
6
7
8
9
10
11
12
13
int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;
    
    int minPrice = prices[0];
    int maxProfit = 0;
    
    for (int i = 1; i < prices.size(); ++i) {
        maxProfit = max(maxProfit, prices[i] - minPrice);
        minPrice = min(minPrice, prices[i]);
    }
    
    return maxProfit;
}

时间复杂度：O(n)
空间复杂度：O(1)

5. 最长递增子序列（LeetCode 300）

给定一个无序的整数数组，找到其中最长递增子序列的长度。

问题分析

1
2
3
输入：[10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，长度为4

DP思路

1
2
3
对于每个位置 i，考虑所有 j < i 的情况：
- 如果 nums[j] < nums[i]，可以接在后面
- 取所有可能中最长的

状态定义

1
dp[i]：以 nums[i] 结尾的最长递增子序列长度

状态转移方程

1
dp[i] = max(dp[j] + 1), 其中 0 <= j < i 且 nums[j] < nums[i]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    
    vector<int> dp(n, 1);  // 初始化为1，每个元素自己构成一个序列
    int maxLen = 1;
    
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    
    return maxLen;
}

时间复杂度：O(n²)
空间复杂度：O(n)

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
nums = [10, 9, 2, 5, 3, 7, 101, 18]

i=0: dp[0]=1  [10]
i=1: dp[1]=1  [9]
i=2: dp[2]=1  [2]
i=3: dp[3]=2  [2,5]  (从2接上)
i=4: dp[4]=2  [2,3]  (从2接上)
i=5: dp[5]=3  [2,5,7] 或 [2,3,7]
i=6: dp[6]=4  [2,5,7,101] 或 [2,3,7,101]
i=7: dp[7]=4  [2,5,7,18] 或 [2,3,7,18]

答案：4

优化：贪心+二分（O(n log n)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;  // tails[i]: 长度为i+1的递增子序列的最小末尾元素
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    
    return tails.size();
}

6. 分割等和子集（LeetCode 416）

给定一个只包含正整数的非空数组，是否可以将这个数组分割成两个子集，使得两个子集的元素和相等？

问题分析

1
2
3
输入：[1,5,11,5]
输出：true
解释：数组可以分割成 [1,5,5] 和 [11]

转化为01背包问题

1
2
3
4
问题转化：能否找到子集，和为总和的一半？

总和 = 22
目标：找到和为11的子集

状态定义

1
dp[i]：是否可以凑出和为 i

状态转移方程

1
2
3
dp[i] = dp[i] || dp[i - nums[j]]
         ↑           ↑
      不选nums[j]  选nums[j]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    
    if (sum % 2 != 0) return false;  // 奇数无法平分
    
    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;  // 和为0总是可以（不选任何元素）
    
    for (int num : nums) {
        // 从后往前遍历，避免重复使用同一元素
        for (int i = target; i >= num; --i) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    
    return dp[target];
}

时间复杂度：O(n × sum)
空间复杂度：O(sum)

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
nums = [1, 5, 11, 5], target = 11

初始：dp[0] = true

处理1：dp[1] = true
      [T, T, F, F, F, F, F, F, F, F, F, F]

处理5：dp[5] = true, dp[6] = dp[6] || dp[1] = true
      [T, T, F, F, F, T, T, F, F, F, F, F]

处理11：dp[11] = true, dp[16]越界忽略
       [T, T, F, F, F, T, T, F, F, F, F, T]

处理5：dp[11]已经是true
      [T, T, F, F, F, T, T, F, F, F, T, T]

答案：dp[11] = true

7. 单词拆分（LeetCode 139）

给定一个非空字符串和一个包含非空单词的列表，判定字符串是否可以被空格拆分为一个或多个在字典中出现的单词。

问题分析

1
2
3
输入：s = "leetcode", wordDict = ["leet", "code"]
输出：true
解释："leetcode" 可以拆分成 "leet code"

状态定义

1
dp[i]：字符串前 i 个字符能否拆分成字典中的单词

状态转移方程

1
dp[i] = dp[j] && (s[j:i] 在字典中), 其中 0 <= j < i

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    int n = s.size();
    
    vector<bool> dp(n + 1, false);
    dp[0] = true;  // 空字符串可以拆分
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (dp[j] && wordSet.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;  // 找到一种拆分方式即可
            }
        }
    }
    
    return dp[n];
}

时间复杂度：O(n² × m)，m为平均单词长度
空间复杂度：O(n)

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
s = "leetcode", wordDict = ["leet", "code"]

i=0: dp[0] = true

i=1: "l" 不在字典 → dp[1] = false
i=2: "le" 不在字典 → dp[2] = false
i=3: "lee" 不在字典 → dp[3] = false
i=4: "leet" 在字典 && dp[0]=true → dp[4] = true
i=5: "eetc" 等都不在字典 → dp[5] = false
...
i=8: "code" 在字典 && dp[4]=true → dp[8] = true

答案：true

8. 完全平方数（LeetCode 279）

给定正整数 n，找到若干个完全平方数使得它们的和等于 n，返回和为 n 的完全平方数的最少数量。

问题分析

1
2
3
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

状态定义

1
dp[i]：和为 i 的完全平方数的最少数量

状态转移方程

1
dp[i] = min(dp[i - j*j] + 1), 其中 j*j <= i

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
int numSquares(int n) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j * j <= i; ++j) {
            dp[i] = min(dp[i], dp[i - j*j] + 1);
        }
    }
    
    return dp[n];
}

时间复杂度：O(n × √n)
空间复杂度：O(n)

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
n = 12

i=0: dp[0] = 0
i=1: dp[1] = dp[0] + 1 = 1  (1 = 1²)
i=2: dp[2] = dp[1] + 1 = 2  (2 = 1² + 1²)
i=3: dp[3] = dp[2] + 1 = 3  (3 = 1² + 1² + 1²)
i=4: dp[4] = dp[0] + 1 = 1  (4 = 2²)
...
i=12: dp[12] = min(dp[11]+1, dp[8]+1, dp[3]+1)
            = min(4, 2, 4) = 3
            (12 = 4 + 4 + 4)

答案：3

空间优化技巧

滚动数组

当 dp[i] 只依赖于 dp[i-1] 和 dp[i-2] 时：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 原始版本 O(n)
vector<int> dp(n);
for (int i = 2; i < n; ++i) {
    dp[i] = dp[i-1] + dp[i-2];
}

// 优化版本 O(1)
int prev2 = ..., prev1 = ...;
for (int i = 2; i < n; ++i) {
    int current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
}

01背包空间优化

1
2
3
4
5
6
7
8
9
10
// 二维DP
vector<vector<bool>> dp(n, vector<bool>(sum, false));

// 优化为一维（从后往前遍历）
vector<bool> dp(sum, false);
for (int num : nums) {
    for (int i = sum; i >= num; --i) {  // 从后往前
        dp[i] = dp[i] || dp[i - num];
    }
}

DP问题分类

线性DP

graph LR
    A[线性DP] --> B[爬楼梯]
    A --> C[打家劫舍]
    A --> D[最大子数组和]
    A --> E[最长递增子序列]
    
    style A fill:#FFE4B5
    style B fill:#90EE90

特点：问题按某种顺序排列，状态转移有明确方向

背包DP

graph LR
    A[背包DP] --> B[分割等和子集]
    A --> C[零钱兑换]
    A --> D[完全平方数]
    
    style A fill:#87CEEB

特点：选或不选的问题

序列DP

graph LR
    A[序列DP] --> B[单词拆分]
    A --> C[解码方法]
    
    style A fill:#DDA0DD

特点：字符串、序列相关

思维导图

graph TD
    A[一维DP] --> B[核心要素]
    A --> C[经典问题]
    A --> D[优化技巧]
    
    B --> B1[状态定义]
    B --> B2[状态转移方程]
    B --> B3[初始化]
    B --> B4[计算顺序]
    
    C --> C1[爬楼梯]
    C --> C2[打家劫舍]
    C --> C3[最长递增子序列]
    C --> C4[背包问题]
    
    D --> D1[滚动数组]
    D --> D2[空间优化]
    D --> D3[记忆化搜索]
    
    style A fill:#FFE4B5
    style C fill:#90EE90
    style D fill:#87CEEB

解题套路

1. 识别DP问题

信号词：

  • 最大/最小值
  • 有多少种方法
  • 是否可能
  • 最长/最短

2. 解题步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1. 定义状态
   - dp[i] 表示什么？
   - 通常是"前i个"或"以i结尾"

2. 找状态转移方程
   - 当前状态如何从之前的状态推导？
   - 画图、列举小例子

3. 初始化
   - dp[0] 或 dp[1] 的值
   - 边界条件

4. 确定计算顺序
   - 从小到大还是从大到小？
   - 一维还是多维遍历？

5. 返回结果
   - 通常是 dp[n] 或 max(dp)

3. 空间优化思路

1
2
3
4
5
如果 dp[i] 只依赖于有限个之前的状态：
→ 用滚动变量代替数组

如果是背包类问题：
→ 从后往前遍历，一维数组即可

总结

核心要点

  1. DP = 记忆化递归：避免重复计算
  2. 状态定义最关键：定义清楚了就成功一半
  3. 画图找规律：小例子推导状态转移方程
  4. 空间可优化：滚动数组降低空间复杂度

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 一维DP通用模板
int solve(/* 输入参数 */) {
    // 1. 状态定义
    vector<int> dp(n + 1);
    
    // 2. 初始化
    dp[0] = ...;
    
    // 3. 状态转移
    for (int i = 1; i <= n; ++i) {
        for (/* 枚举决策 */) {
            dp[i] = /* 转移方程 */;
        }
    }
    
    // 4. 返回结果
    return dp[n];
}

推荐题目

入门级：

进阶级：

高级：

推荐阅读：