动态规划讲解（炒鸡详细）--未完工

科技起源

2026-05-03 18:05:26

发布于：河北

16阅读

0回复

0点赞

本篇文章只基于我这个学dp不到半年的萌新的一些看法

※ 本篇讲解的是递推解决dp问题的方式，有些的不好的直接喷 ※

相信大家对递推不陌生，不在此介绍（对递推陌生的先了解去）

那我就直接开始分享了？

1 什么是动态规划（Dynamic Programming, 简称DP）

1.1 个人看法

个人认为，动态规划就是：把一个复杂的大问题，拆成很多简单的小问题
有两个关键操作：

先把小问题的答案算出来并记录
后面需要这个答案的时候，直接使用

就像你做数学题，第二小问的答案中的一部分可能是由第一小问的答案推导来的

1.2 标准定义

动态规划，是一种拆分复杂问题、记忆化存储子问题解的算法思想。
适用于满足最优子结构和无后效性的问题

1.2.1 动态规划的特点

最优子结构：大问题的最优解，可以由若干个子问题的最优解推导得到；
无后效性：当前阶段的结果，只和前面已经算完的阶段有关，和未来还没做的选择没有任何关系；
核心思想：分治拆分 + 记忆化复用，避免暴力枚举带来的大量重复计算，提升时间效率。

2 动态规划求解步骤

个人认为，可以通过以下 $4$ 步解决

2.1 状态定义（设计状态）

在第一步中，我们会定义一个数组（通常为f或dp）
我们要设置dp[i]/dp[i][j]/dp[i][j][k]当做状态，也就是说我们要清楚dp数组中当前这一项代表什么，只有清楚它的定义，我们才能进行求解状态转移方程
那么如何设计状态呢？

2.1.1 先考虑这道题需要你求什么答案？

如爬楼梯这道经典例题
题目要求找到爬到第 $n$ 阶的方案数，故设计dp[i]为爬到第 $i$ 阶的方案数

2.1.2 设计状态的核心原则

能代表一个完整小问题
能从小的推大的
不多余
满足无后效性（就是说这一项不管以后怎么选）

2.1.3 常用状态设计方案（ $dp_i$ 或 ${dp_i}_j$ 表示？）

2.1.3.1 一维dp

表示前 $i$ 项的最优答案
表示到位置 $i$ 时的最值/方案数

2.1.3.2 二维dp

表示区间 $[i, j]$ 之间的最优解
表示选前 $i$ 个物品，容量为 $j$ 时的最大价值（背包问题！）
表示处理到第 $i$ 个或第 $i$ 个之前，限制为 $j$ 时的答案
到达位置 $i_j$ 时的答案

2.1.4 提示：

对于高阶dp来说，dp开三维数组甚至四维数组都是常见的，下文我会讲解动态规划的优化

2.2 设置初始值（确定初始边界）

2.2.1 理解

一般来说，问题最小，最开头，不用计算就知道答案的位置需要初始化
位置如： $i = 0$ / $j = 0$ / $i = 1$ / $j = 1$ 这些开头位置或者全局初始化
初始化值如： $INF，-INF,0,1$
额外提一嘴，如果你想要全局初始化，可以使用如下函数：

// 设置为0
memset(数组名,0,sizeof(数组名));
// 设置为极大数
memset(数组名,0x3f,sizeof(数组名));
// 设置为极小数
memset(数组名,-0x3f,sizeof(数组名));
// 设置为任何数
fill(起始地址,结束地址,数字)

2.2.2 举例

还是以爬楼梯这道题为例
从第 $3$ 项以后的内容都可以由前面推导而来，因此设置：

dp[0] = 1;// 到第0级只有一种方案：0
dp[1] = 1;// 到第1级只有一种方案：0->1
dp[2] = 2;// 到第2级只有两种方案：0->1->2或者0->2

2.3 推导状态转移方程

2.3.1 先理解什么是状态转移方程

状态转移方程就是：现在这个 dp 值，是从前面哪几个旧 dp 值，通过加、减、取最大、取最小、求和、求积变过来的式子。推导状态转移方程就是：看当前情况有几种选择，每种选择对应前面哪个状态，再把式子写出来。

2.3.2 通用步骤

2.3.2.1 分析当前这一步有几种可能，把所有可能的方法列出来

比如：

选/不选这个物品
从某个方向走过来
从前面的某一项走过来
区间分成左边/右边一段

对于爬楼梯这道题，每一级都可能从前面的 $1$ $2$ $3$ 项过来

2.3.2.2 每种选择，找前面可能过来的状态

比如：爬楼梯这道题
连跳 $1$ 步，从 $i - 1$ 来
连跳 $2$ 步，从 $i - 2$ 来
连跳 $3$ 步，从 $i - 3$ 来

2.3.2.3 根据题目要求，选运算规则

看题目问什么，套对应运算：

求总方案数、总走法、总数量 $\longrightarrow$ 把几种情况相加
求最大值、最大价值 $\longrightarrow$ 几种情况取max
求最小值、最少花费 $\longrightarrow$ 几种情况取min
拼接区间答案 $\longrightarrow$ 左右区间值相加 / 合并

依旧对于爬楼梯这道题，要求总走法，所以相加即可

2.4 取最终答案

还记得第2.1部分讲解的设计状态吗？
我们要找到能代表整道题答案的那一项：
可能存在：

$dp_n$
${dp_n}_m$
$\max\limits_{1\le i\le n} dp[i]$
$\max\limits_{1\le j\le m} dp[n][j]$
$\max\limits_{1\le i\le n} dp[i][m]$
$\max\limits_{\substack{1\le i\le n \\ 1\le j\le m}} dp[i][j]$

最终输出答案即可

中场休息

就在刚刚，我们了解了什么是dp，以及做dp题的步骤
有没有感觉明了一些了？

大家想练题，可以去ACGO的学习部分找到相应题目
也可以去题库中找到相应题目练练手
给大家推荐一下练题内容：

学习内容	学习阶段
简单线性动态规划	GESP6级
简单背包动态规划
计数动态规划
简单多维动态规划
区间动态规划	GESP7级、CSP-J常考
复杂多维动态规划
状态压缩动态规划
复杂线性动态规划
复杂背包动态规划
简单树形动态规划
简单动态规划的优化（如单调队列、滚动数组）
复杂树形动态规划	GESP8级、CSP-S常考、甚至NOIP
数位动态规划
复杂状态压缩动态规划
概率动态规划
期望动态规划
复杂动态规划的优化（如斜率优化动态规划）

有帮助，赞一个

去预览

0/2000

全部评论 2

Xylophone
NOIP 岀轮廓线，只有假肢沉能进队了

5天前来自广东
0
- 科技起源
  回复
  Xylophone
  行，我不清楚，我就是一只啥也不会的入。我改一下
  
  5天前来自河北
  0
Xylophone
这是你写的吗

5天前来自广东
0
- 科技起源
  回复
  Xylophone
  是我自己写的
  
  5天前来自河北
  0