当前位置：首页 > news >正文

what？动态规划？

news 2026/5/11 20:07:24

动态规划入门：从原理到实战，吃透基础算法

动态规划（Dynamic Programming，简称 DP）是算法领域的核心思想之一，也是面试、竞赛中的高频考点。它并非单一算法，而是一种 “化繁为简” 的解题思路 —— 通过拆解复杂问题为可解决的子问题，存储子问题的解以避免重复计算，最终推导出原问题的最优解。本文将从核心原理、通用解题步骤、经典案例到实战技巧，全方位拆解动态规划的基础逻辑，所有示例均采用 C++ 实现，帮你真正吃透 DP 底层逻辑。

一、动态规划的核心：解决 “重复计算” 的痛点

在理解 DP 之前，我们先看一个经典问题：求斐波那契数列的第 n 项。斐波那契数列定义为：f(0)=0，f(1)=1，f(n)=f(n-1)+f(n-2)（n≥2）。

暴力递归的问题

如果用纯递归实现：

cpp

运行

int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }

看似简洁，但存在致命缺陷：重叠子问题。计算fib(5)时，需要计算fib(4)和fib(3)；计算fib(4)又需要fib(3)和fib(2)——fib(3)被重复计算了两次。随着 n 增大，重复计算的子问题呈指数级增长，时间复杂度达到 O (2ⁿ)，n=40 时就会出现明显卡顿。

动态规划的优化思路

DP 的核心就是解决 “重复计算”：

最优子结构：原问题的最优解包含子问题的最优解（比如fib(n)的解依赖fib(n-1)和fib(n-2)的解）；
记忆化存储：用数组 / 哈希表记录已计算的子问题解，后续直接调用，无需重复计算。

这两点让 DP 能将时间复杂度从暴力递归的 O (2ⁿ) 优化到 O (n)，效率提升数个量级。

二、动态规划解题四步法（通用模板）

无论多难的 DP 问题，都能拆解为以下四步，这是新手入门的 “万能框架”：

第一步：定义状态（DP 的 “记忆载体”）

状态是 DP 的核心，需要明确：dp[i]或dp[i][j]代表什么具体含义？

一维 DP：dp[i]可表示 “前 i 个元素的最优解”“到达第 i 个位置的方案数”；
二维 DP：dp[i][j]可表示 “从 (0,0) 到 (i,j) 的最短路径和”“用前 i 个物品装满容量 j 的背包的最大价值”。

关键原则：状态定义必须贴合 “子问题”，让后续的递推关系能自然成立。

第二步：推导递推公式（DP 的 “灵魂”）

递推公式描述 “大问题如何由小问题推导”，是 DP 解题的核心逻辑。比如爬楼梯问题（一次能爬 1 或 2 级台阶，求到第 n 级的方案数）：

状态定义：dp[i]= 到达第 i 级台阶的方案数；
递推逻辑：到达第 i 级只能从 i-1 级（爬 1 级）或 i-2 级（爬 2 级）过来，因此dp[i] = dp[i-1] + dp[i-2]。

第三步：初始化状态（边界条件）

递推公式需要 “起点”，必须初始化最小子问题的解。比如爬楼梯：

dp[1] = 1（1 级台阶只有 1 种走法）；
dp[2] = 2（2 级台阶有 “1+1” 或 “2” 两种走法）。

第四步：确定遍历顺序（避免依赖未计算的状态）

遍历顺序需保证：计算dp[i]时，其依赖的dp[i-1]/dp[i-2]已经被计算完成。比如爬楼梯需 “从前往后” 遍历（i 从 3 到 n），而 0-1 背包则需要 “从后往前” 遍历（避免物品重复选取）。

三、经典案例拆解：从基础到进阶

案例 1：斐波那契数列（一维 DP 入门）

解题步骤

状态定义：dp[i]表示第 i 项斐波那契数；
递推公式：dp[i] = dp[i-1] + dp[i-2]；
初始化：dp[0] = 0，dp[1] = 1；
遍历顺序：从 2 到 n 正序遍历。

C++ 实现（基础版 + 空间优化版）

cpp

运行

#include <iostream> #include <vector> using namespace std; // 基础版：O(n) 时间，O(n) 空间 int fib(int n) { if (n <= 1) return n; // 定义状态数组 vector<int> dp(n + 1); // 初始化 dp[0] = 0; dp[1] = 1; // 递推计算 for (int i = 2; i <= n; ++i) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } // 优化版：O(n) 时间，O(1) 空间（滚动变量） int fib_optimized(int n) { if (n <= 1) return n; int a = 0, b = 1; // a=dp[i-2], b=dp[i-1] for (int i = 2; i <= n; ++i) { int temp = b; b = a + b; a = temp; } return b; } int main() { int n = 10; cout << "斐波那契数列第 " << n << " 项（基础版）：" << fib(n) << endl; cout << "斐波那契数列第 " << n << " 项（优化版）：" << fib_optimized(n) << endl; return 0; }

案例 2：爬楼梯（一维 DP 经典应用）

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

解题步骤

状态定义：dp[i]表示到达第 i 级台阶的方法数；
递推公式：dp[i] = dp[i-1] + dp[i-2]（最后一步爬 1 级或 2 级）；
初始化：dp[1] = 1，dp[2] = 2；
遍历顺序：从 3 到 n 正序遍历。

C++ 实现

cpp

运行

#include <iostream> #include <vector> using namespace std; 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]; } // 空间优化版 int climbStairs_optimized(int n) { if (n <= 2) return n; int a = 1, b = 2; for (int i = 3; i <= n; ++i) { int temp = b; b = a + b; a = temp; } return b; } int main() { int n = 5; cout << "爬 " << n << " 级台阶的方法数（基础版）：" << climbStairs(n) << endl; cout << "爬 " << n << " 级台阶的方法数（优化版）：" << climbStairs_optimized(n) << endl; return 0; }

案例 3：最长递增子序列（LIS，一维 DP 进阶）

问题描述：给你一个整数数组 nums，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

解题步骤

状态定义：dp[i]表示以 nums [i] 结尾的最长递增子序列的长度；
递推公式：遍历 j 从 0 到 i-1，若nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j] + 1)；
初始化：dp[i] = 1（每个元素自身是长度为 1 的子序列）；
遍历顺序：外层 i 从 1 到 n-1，内层 j 从 0 到 i-1。

C++ 实现

cpp

运行

#include <iostream> #include <vector> #include <algorithm> using namespace std; int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; // 定义状态数组 vector<int> dp(n, 1); int max_len = 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); } } max_len = max(max_len, dp[i]); } return max_len; } int main() { vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18}; cout << "最长递增子序列长度：" << lengthOfLIS(nums) << endl; return 0; }

案例 4：0-1 背包问题（二维 DP 核心）

问题描述：有 N 件物品和一个容量为 V 的背包。每件物品只能用一次。第 i 件物品的体积是 v [i]，价值是 w [i]。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

解题步骤

状态定义：dp[i][j]表示前 i 件物品，背包容量为 j 时的最大价值；
递推公式：
- 不选第 i 件物品：dp[i][j] = dp[i-1][j]；
- 选第 i 件物品（需 j ≥ v [i]）：dp[i][j] = max(dp[i][j], dp[i-1][j - v[i]] + w[i])；
初始化：dp[0][j] = 0（0 件物品时价值为 0），dp[i][0] = 0（容量为 0 时价值为 0）；
遍历顺序：外层 i 从 1 到 N，内层 j 从 1 到 V。

C++ 实现（基础版 + 空间优化版）

cpp

运行

#include <iostream> #include <vector> #include <algorithm> using namespace std; // 基础版：二维数组，O(N*V) 时间，O(N*V) 空间 int knapsack_01(vector<int>& v, vector<int>& w, int V) { int N = v.size(); // 定义状态数组：dp[i][j] 前i件物品，容量j的最大价值 vector<vector<int>> dp(N + 1, vector<int>(V + 1, 0)); // 递推计算 for (int i = 1; i <= N; ++i) { for (int j = 1; j <= V; ++j) { // 不选第i件物品 dp[i][j] = dp[i-1][j]; // 选第i件物品（需容量足够） if (j >= v[i-1]) { // v[i-1] 是第i件物品的体积（数组从0开始） dp[i][j] = max(dp[i][j], dp[i-1][j - v[i-1]] + w[i-1]); } } } return dp[N][V]; } // 优化版：一维数组，O(N*V) 时间，O(V) 空间（逆序遍历） int knapsack_01_optimized(vector<int>& v, vector<int>& w, int V) { int N = v.size(); vector<int> dp(V + 1, 0); for (int i = 0; i < N; ++i) { // 逆序遍历：避免重复选取同一物品 for (int j = V; j >= v[i]; --j) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } return dp[V]; } int main() { // 物品体积 vector<int> v = {2, 3, 4, 5}; // 物品价值 vector<int> w = {3, 4, 5, 6}; // 背包容量 int V = 8; cout << "0-1背包最大价值（二维版）：" << knapsack_01(v, w, V) << endl; cout << "0-1背包最大价值（一维版）：" << knapsack_01_optimized(v, w, V) << endl; return 0; }

四、动态规划实战技巧与避坑指南

1. 空间优化技巧

一维 DP：用 “滚动变量” 替代数组（如斐波那契、爬楼梯的 O (1) 空间优化）；
二维 DP：压缩为一维数组（如 0-1 背包的逆序遍历），核心是 “覆盖不需要的历史状态”；
特殊场景：状态仅依赖相邻行 / 列时，可用 “滚动数组”（如二维 DP 压缩为两行）。

2. 新手常见误区

状态定义模糊：比如 LIS 问题中，若错误定义dp[i]为 “前 i 个元素的最长递增子序列长度”，会导致递推公式无法推导。正确做法是让dp[i]绑定 “以 nums [i] 结尾” 的条件；
递推公式遗漏边界：比如 0-1 背包未判断j >= v[i]，会导致数组越界；
遍历顺序错误：0-1 背包一维优化时，若正序遍历 j，会导致同一物品被多次选取；
过度追求优化：新手优先保证代码正确性，再优化空间 / 时间，比如先写二维背包，再尝试一维压缩。