动态规划讲解(炒鸡详细)--未完工
2026-05-03 18:05:26
发布于:河北
本篇文章只基于我这个学dp不到半年的萌新的一些看法
※ 本篇讲解的是递推解决dp问题的方式,有些的不好的直接喷 ※
相信大家对递推不陌生,不在此介绍(对递推陌生的先了解去)
那我就直接开始分享了?
1 什么是动态规划(Dynamic Programming, 简称DP)
1.1 个人看法
个人认为,动态规划就是:把一个复杂的大问题,拆成很多简单的小问题
有两个关键操作:
- 先把小问题的答案算出来并记录
- 后面需要这个答案的时候,直接使用
就像你做数学题,第二小问的答案中的一部分可能是由第一小问的答案推导来的
1.2 标准定义
动态规划,是一种拆分复杂问题、记忆化存储子问题解的算法思想。
适用于满足最优子结构和无后效性的问题
1.2.1 动态规划的特点
- 最优子结构:大问题的最优解,可以由若干个子问题的最优解推导得到;
- 无后效性:当前阶段的结果,只和前面已经算完的阶段有关,和未来还没做的选择没有任何关系;
- 核心思想:分治拆分 + 记忆化复用,避免暴力枚举带来的大量重复计算,提升时间效率。
2 动态规划求解步骤
个人认为,可以通过以下 步解决
2.1 状态定义(设计状态)
在第一步中,我们会定义一个数组(通常为f或dp)
我们要设置dp[i]/dp[i][j]/dp[i][j][k]当做状态,也就是说我们要清楚dp数组中当前这一项代表什么,只有清楚它的定义,我们才能进行求解状态转移方程
那么如何设计状态呢?
2.1.1 先考虑这道题需要你求什么答案?
如 爬楼梯 这道经典例题
题目要求找到爬到第 阶的方案数,故设计dp[i]为爬到第 阶的方案数
2.1.2 设计状态的核心原则
- 能代表一个完整小问题
- 能从小的推大的
- 不多余
- 满足无后效性(就是说这一项不管以后怎么选)
2.1.3 常用状态设计方案( 或 表示?)
2.1.3.1 一维dp
- 表示前 项的最优答案
- 表示到位置 时的最值/方案数
2.1.3.2 二维dp
- 表示区间 之间的最优解
- 表示选前 个物品,容量为 时的最大价值(背包问题!)
- 表示处理到第 个或第 个之前,限制为 时的答案
- 到达位置 时的答案
2.1.4 提示:
对于高阶dp来说,dp开三维数组甚至四维数组都是常见的,下文我会讲解动态规划的优化
2.2 设置初始值(确定初始边界)
2.2.1 理解
一般来说,问题最小,最开头,不用计算就知道答案的位置需要初始化
位置如: / / / 这些开头位置 或者 全局初始化
初始化值如:
额外提一嘴,如果你想要全局初始化,可以使用如下函数:
// 设置为0
memset(数组名,0,sizeof(数组名));
// 设置为极大数
memset(数组名,0x3f,sizeof(数组名));
// 设置为极小数
memset(数组名,-0x3f,sizeof(数组名));
// 设置为任何数
fill(起始地址,结束地址,数字)
2.2.2 举例
还是以 爬楼梯 这道题为例
从第 项以后的内容都可以由前面推导而来,因此设置:
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 分析当前这一步有几种可能,把所有可能的方法列出来
比如:
- 选/不选这个物品
- 从某个方向走过来
- 从前面的某一项走过来
- 区间分成左边/右边一段
对于 爬楼梯 这道题,每一级都可能从前面的 项过来
2.3.2.2 每种选择,找前面可能过来的状态
比如: 爬楼梯 这道题
连跳 步,从 来
连跳 步,从 来
连跳 步,从 来
2.3.2.3 根据题目要求,选运算规则
看题目问什么,套对应运算:
- 求总方案数、总走法、总数量 把几种情况相加
- 求最大值、最大价值 几种情况取max
- 求最小值、最少花费 几种情况取min
- 拼接区间答案 左右区间值相加 / 合并
依旧对于 爬楼梯 这道题,要求总走法,所以相加即可
2.4 取最终答案
还记得第2.1部分讲解的设计状态吗?
我们要找到能代表整道题答案的那一项:
可能存在:
最终输出答案即可
中场休息
就在刚刚,我们了解了什么是dp,以及做dp题的步骤
有没有感觉明了一些了?
大家想练题,可以去ACGO的学习部分找到相应题目
也可以去题库中找到相应题目练练手
给大家推荐一下练题内容:
| 学习内容 | 学习阶段 |
|---|---|
| 简单线性动态规划 | GESP6级 |
| 简单背包动态规划 | |
| 计数动态规划 | |
| 简单多维动态规划 | |
| 区间动态规划 | GESP7级、CSP-J常考 |
| 复杂多维动态规划 | |
| 状态压缩动态规划 | |
| 复杂线性动态规划 | |
| 复杂背包动态规划 | |
| 简单树形动态规划 | |
| 简单动态规划的优化(如单调队列、滚动数组) | |
| 复杂树形动态规划 | GESP8级、CSP-S常考、甚至NOIP |
| 数位动态规划 | |
| 复杂状态压缩动态规划 | |
| 概率动态规划 | |
| 期望动态规划 | |
| 复杂动态规划的优化(如斜率优化动态规划) |
全部评论 2
NOIP 岀轮廓线,只有假肢沉能进队了
5天前 来自 广东
0行,我不清楚,我就是一只啥也不会的入。我改一下
5天前 来自 河北
0
这是你写的吗
5天前 来自 广东
0是我自己写的
5天前 来自 河北
0



















有帮助,赞一个