本篇文章只基于我这个学DP不到半年的萌新的一些看法
※ 本篇讲解的是递推解决DP问题的方式,有些的不好的直接喷 ※
相信大家对递推不陌生,不在此介绍(对递推陌生的先了解去)
那我就直接开始分享了?
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1 什么是动态规划(DYNAMIC PROGRAMMING, 简称DP)
1.1 个人看法
个人认为,动态规划就是:把一个复杂的大问题,拆成很多简单的小问题
有两个关键操作:
* 先把小问题的答案算出来并记录
* 后面需要这个答案的时候,直接使用
就像你做数学题,第二小问的答案中的一部分可能是由第一小问的答案推导来的
1.2 标准定义
动态规划,是一种拆分复杂问题、记忆化存储子问题解的算法思想。
适用于满足最优子结构和无后效性的问题
1.2.1 动态规划的特点
1. 最优子结构:大问题的最优解,可以由若干个子问题的最优解推导得到;
2. 无后效性:当前阶段的结果,只和前面已经算完的阶段有关,和未来还没做的选择没有任何关系;
3. 核心思想:分治拆分 + 记忆化复用,避免暴力枚举带来的大量重复计算,提升时间效率。
2 动态规划求解步骤
> 个人认为,可以通过以下 444 步解决
2.1 状态定义(设计状态)
在第一步中,我们会定义一个数组(通常为f或dp)
我们要设置dp[i]/dp[i][j]/dp[i][j][k]当做状态,也就是说我们要清楚dp数组中当前这一项代表什么,只有清楚它的定义,我们才能进行求解状态转移方程
那么如何设计状态呢?
2.1.1 先考虑这道题需要你求什么答案?
如 爬楼梯 这道经典例题
题目要求找到爬到第 nnn 阶的方案数,故设计dp[i]为爬到第 iii 阶的方案数
2.1.2 设计状态的核心原则
1. 能代表一个完整小问题
2. 能从小的推大的
3. 不多余
4. 满足无后效性(就是说这一项不管以后怎么选)
2.1.3 常用状态设计方案(DPIDP_IDPI 或 DPIJ{DP_I}_JDPI J 表示?)
2.1.3.1 一维DP
* 表示前 iii 项的最优答案
* 表示到位置 iii 时的最值/方案数
2.1.3.2 二维DP
* 表示区间 [i,j][i, j][i,j] 之间的最优解
* 表示选前 iii 个物品,容量为 jjj 时的最大价值(背包问题!)
* 表示处理到第 iii 个或第 iii 个之前,限制为 jjj 时的答案
* 到达位置 iji_jij 时的答案
2.1.4 提示:
对于高阶dp来说,dp开三维数组甚至四维数组都是常见的,下文我会讲解动态规划的优化
2.2 设置初始值(确定初始边界)
2.2.1 理解
一般来说,问题最小,最开头,不用计算就知道答案的位置需要初始化
位置如:i=0i = 0i=0 / j=0j = 0j=0 / i=1i = 1i=1 / j=1j = 1j=1 这些开头位置 或者 全局初始化
初始化值如:INF,−INF,0,1INF,-INF,0,1INF,−INF,0,1
额外提一嘴,如果你想要全局初始化,可以使用如下函数:
2.2.2 举例
还是以 爬楼梯 这道题为例
从第 333 项以后的内容都可以由前面推导而来,因此设置:
2.3 推导状态转移方程
2.3.1 先理解什么是状态转移方程
状态转移方程就是:现在这个 dp 值,是从前面哪几个旧 dp 值,通过加、减、取最大、取最小、求和、求积变过来的式子。推导状态转移方程就是:看当前情况有几种选择,每种选择对应前面哪个状态,再把式子写出来。
2.3.2 通用步骤
2.3.2.1 分析当前这一步有几种可能,把所有可能的方法列出来
比如:
* 选/不选这个物品
* 从某个方向走过来
* 从前面的某一项走过来
* 区间分成左边/右边一段
对于 爬楼梯 这道题,每一级都可能从前面的 111 222 333 项过来
2.3.2.2 每种选择,找前面可能过来的状态
比如: 爬楼梯 这道题
连跳 111 步,从 i−1i - 1i−1 来
连跳 222 步,从 i−2i - 2i−2 来
连跳 333 步,从 i−3i - 3i−3 来
2.3.2.3 根据题目要求,选运算规则
看题目问什么,套对应运算:
* 求总方案数、总走法、总数量 ⟶\longrightarrow⟶ 把几种情况相加
* 求最大值、最大价值 ⟶\longrightarrow⟶ 几种情况取max
* 求最小值、最少花费 ⟶\longrightarrow⟶ 几种情况取min
* 拼接区间答案 ⟶\longrightarrow⟶ 左右区间值相加 / 合并
依旧对于 爬楼梯 这道题,要求总走法,所以相加即可
2.4 取最终答案
还记得第2.1部分讲解的设计状态吗?
我们要找到能代表整道题答案的那一项:
可能存在:
* dpndp_ndpn
* dpnm{dp_n}_mdpn m
* max1≤i≤ndp[i]\max\limits_{1\le i\le n} dp[i]1≤i≤nmax dp[i]
* max1≤j≤mdp[n][j]\max\limits_{1\le j\le m} dp[n][j]1≤j≤mmax dp[n][j]
* max1≤i≤ndp[i][m]\max\limits_{1\le i\le n} dp[i][m]1≤i≤nmax dp[i][m]
* max1≤i≤n1≤j≤mdp[i][j]\max\limits_{\substack{1\le i\le n \\ 1\le j\le m}} dp[i][j]1≤i≤n1≤j≤m max dp[i][j]
最终输出答案即可
中场休息
就在刚刚,我们了解了什么是dp,以及做dp题的步骤
有没有感觉明了一些了?
大家想练题,可以去ACGO的学习部分找到相应题目
也可以去题库中找到相应题目练练手
给大家推荐一下练题内容:
学习内容 学习阶段 简单线性动态规划 GESP6级 简单背包动态规划 计数动态规划 简单多维动态规划 区间动态规划 GESP7级、CSP-J常考 复杂多维动态规划 状态压缩动态规划 复杂线性动态规划 复杂背包动态规划 简单树形动态规划 简单动态规划的优化(如单调队列、滚动数组) 复杂树形动态规划 GESP8级、CSP-S常考、甚至NOIP 数位动态规划 复杂状态压缩动态规划 概率动态规划 期望动态规划 复杂动态规划的优化(如斜率优化动态规划)