网站导航
> 技术文档 > 看一遍就懂：动态规划详解

看一遍就懂：动态规划详解

网友: 技术文档 2025-09-02 19:12:48

目录

前言

什么是动态规划？

核心思想

例子1 — 青蛙跳台阶问题

1. 暴力递归解法（超时示范）

2. 带备忘录的递归（自顶向下）

3. 动态规划（自底向上）

动态规划解题套路总结

经典案例：最长递增子序列（LIS）

1. 穷举分析

2. 状态转移方程

3. 代码实现

总结

前言

刷 LeetCode 的时候，经常会遇到动态规划（DP）类型题目。动态规划既经典又有技巧，大厂面试题里常常出现。很多同学第一次接触时会觉得很抽象，今天我们就来一起剖析动态规划的套路，带你从入门到精通。

什么是动态规划？

动态规划（Dynamic Programming，简称 DP）是一种解决复杂问题的算法设计方法，其核心思想是将原问题拆解成相对简单的子问题，逐个解决并保存子问题的结果，避免重复计算，从而高效地求解问题。

动态规划适合具有以下两个性质的问题：

  1. 重叠子问题（Overlapping Subproblems）：子问题会重复出现；

  2. 最优子结构（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 std::unordered_map 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)，只保存最近两个状态。

动态规划解题套路总结

  1. 穷举分析：尝试列出问题所有可能的状态和解法。

  2. 确定边界：找出最小问题的解。

  3. 找规律，确定最优子结构：分析问题是否能通过子问题的解推导。

  4. 写状态转移方程：数学形式描述状态之间的关系。

  5. 代码实现：从边界状态开始迭代计算，得到最终答案。

经典案例：最长递增子序列（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.length

3. 代码实现

#include #include int lengthOfLIS(std::vector& nums){ if (nums.empty()) return 0; int n = nums.size(); std::vector 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;}

总结

动态规划是一种将问题“分而治之”的高效方法，核心在于拆分子问题、保存中间结果、避免重复计算。它适用于有重叠子问题和最优子结构的问题。通过本篇文章的青蛙跳台阶与最长递增子序列两个案例，我们掌握了从状态定义、边界处理、状态转移方程推导到代码实现的完整套路。只要理解了这些关键步骤，动态规划其实并不难，是值得深入掌握的重要算法技能。

网络标签：

相关问题