看一遍就懂：动态规划详解
目录
前言
刷 LeetCode 的时候，经常会遇到动态规划（DP）类型题目。动态规划既经典又有技巧，大厂面试题里常常出现。很多同学第一次接触时会觉得很抽象，今天我们就来一起剖析动态规划的套路，带你从入门到精通。
什么是动态规划？
动态规划（Dynamic Programming，简称 DP）是一种解决复杂问题的算法设计方法，其核心思想是将原问题拆解成相对简单的子问题，逐个解决并保存子问题的结果，避免重复计算，从而高效地求解问题。
动态规划适合具有以下两个性质的问题：重叠子问题（Overlapping Subproblems）：子问题会重复出现；最优子结构（Optimal Substructure）：原问题的最优解包含子问题的最优解。
简单理解就是“记住求过的解，避免重复计算”，比如经典的斐波那契数列就是动态规划的入门例子。
核心思想
- 拆分子问题：将大问题拆成子问题。
- 保存历史结果：用数组、哈希表等结构缓存已经算过的子问题结果。
- 避免重复计算：子问题只计算一次，节省时间。
举个例子：
计算1+1+1+1+1+1+1+1的值是8，如果我在这个基础上再加一个1，结果就是9，不用重新计算整个加法过程，直接利用之前的结果。
这就是动态规划节省计算的精髓。
例子1 — 青蛙跳台阶问题
题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求跳上10级台阶的跳法总数。
1. 暴力递归解法（超时示范）
定义 f(n) 表示跳到第 n 级台阶的跳法数。根据题意：
f(n) = f(n-1) + f(n-2)边界条件：
f(1) = 1 f(2) = 2代码实现：
int numWays(int n) { if (n == 1) return 1; if (n == 2) return 2; return numWays(n - 1) + numWays(n - 2); }递归树：
问题：当 n 很大时，递归树节点数爆炸，时间复杂度是指数级 O(2^n)，容易超时。
2. 带备忘录的递归（自顶向下）
利用一个哈希表或数组存储已经计算过的 f(n)，避免重复计算。
代码实现：
#include <unordered_map> std::unordered_map<int, int> memo; int numWays(int n) { if (n == 0) return 1; if (n == 1) return 1; if (n == 2) return 2; if (memo.count(n)) return memo[n]; memo[n] = (numWays(n - 1) + numWays(n - 2)) % 1000000007; return memo[n]; }时间复杂度降低到 O(n)，性能大幅提升。
3. 动态规划（自底向上）
从小问题开始迭代到大问题，状态转移方程同上。
int numWays(int n) { if (n <= 1) return 1; if (n == 2) return 2; int a = 1, b = 2, res = 0; for (int i = 3; i <= n; ++i) { res = (a + b) % 1000000007; a = b; b = res; } return res; } 空间复杂度可以优化为 O(1)，只保存最近两个状态。
动态规划解题套路总结
- 穷举分析：尝试列出问题所有可能的状态和解法。
- 确定边界：找出最小问题的解。
- 找规律，确定最优子结构：分析问题是否能通过子问题的解推导。
- 写状态转移方程：数学形式描述状态之间的关系。
- 代码实现：从边界状态开始迭代计算，得到最终答案。
经典案例：最长递增子序列（LIS）
题目：给定数组 nums，找出其中最长严格递增子序列的长度。
示例：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 （最长递增子序列为 [2,3,7,101]）1. 穷举分析
dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。
- 单个元素序列长度为1，边界：
dp[0] = 1。 - 对每个
nums[i]，遍历之前所有元素nums[j] (j < i)：- 如果
nums[j] < nums[i]，说明可以把nums[i]接到以nums[j]结尾的序列后面， - 更新
dp[i] = max(dp[i], dp[j] + 1)。
- 如果
2. 状态转移方程
dp[i] = max{dp[j]} + 1, 其中 0 ≤ j < i 且 nums[j] < nums[i]边界条件：
dp[0] = 1最终答案为：
max(dp[i])，0 ≤ i < nums.length3. 代码实现
#include <vector> #include <algorithm> int lengthOfLIS(std::vector<int>& nums) { if (nums.empty()) return 0; int n = nums.size(); std::vector<int> dp(n, 1); // 每个元素至少自成一个序列 int res = 1; for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) { dp[i] = std::max(dp[i], dp[j] + 1); } } res = std::max(res, dp[i]); } return res; } 总结
动态规划是一种将问题“分而治之”的高效方法，核心在于拆分子问题、保存中间结果、避免重复计算。它适用于有重叠子问题和最优子结构的问题。通过本篇文章的青蛙跳台阶与最长递增子序列两个案例，我们掌握了从状态定义、边界处理、状态转移方程推导到代码实现的完整套路。只要理解了这些关键步骤，动态规划其实并不难，是值得深入掌握的重要算法技能。
