难度 | 算法s | 日期 | 题目链接 |
---|---|---|---|
普及− | DP | 2025-05-21 | https://luogu.com.cn/problem/P1044 |
因为本人 DP 很差,故撰此文巩固一下。
本文是对 P1044 [NOIP 2003 普及组] 栈 题解 的详细解释。
写的很直白了。。。几乎没有理解难度吧。。。
DP 状态设计
二维 DP 做法,\(dp[x][y]\) 表示:
- 有 \(x\) 个元素未入栈,意味着可以入栈 \(x\) 次。
- 有 \(y\) 个元素在栈内,意味着可以出栈 \(y\) 次。
(注意这里没有明确 \(dp[...][...]\) 表示什么,只是设计了状态,下面讲怎么设计 \(dp[...][...]\) 要表示的值。)
将这样转移:
上图:“出入栈操作,状态转移过程”
然后呢?怎么算?
初始时,我们有一个状态 \(dp[n][0]\),也就是有 \(n\) 次入栈机会,但是从未执行过入栈操作。
接下来,我们进行操作, \(dp[x][y]\) 中 \(x\) 和 \(y\) 的值不断变化...
然后我们到达了一个末状态 \(dp[0][0]\),这时候我们没法进行更多操作了。
其实我们要计算的就是从初状态到末状态,有多少种“路径”,即所有可能的“操作序列”。
接下来我们要从末状态 \(Q\) 往回推,求可能的路径数。
很明显,从子状态 \(H\) 和 \(I\) 到末状态 \(Q\) 都只有一条路径。(边界状态)
现在来看这三个点:\(A\)、\(D\)、\(E\)。
很明显:
\(A\) 到末状态 \(Q\) 的路径数 \(=\) \(D\) 的路径数 \(+\) \(E\) 的路径数
归纳一下:
\(X\) 的路径数 \(=\) \(X\) 所有子状态的路径数之和
用这个公式从 \(Q\) 往回推,直到 \(P\) 就好了。
好,接下来DP。
决定了,\(dp[x][y]\) 就表示:还有 \(x\) 个元素要入栈,\(y\) 个元素要出栈,此时通向末状态可能的路径数。
(注意用词,这里用“还有...要”,暗示了最终要导向末状态 \(dp[0][0]\),必须把可以入栈的机会 \(x\) 和可以出栈的机会 \(y\) 都用完。)
一图以蔽之。
之前我们不是推了“出入栈操作,状态转移过程”吗,其实 DP 的方向就是恰好相反。
很容易得到状态转移公式:
\(dp[x][y]=dp[x-1][y+1]+dp[x][y-1]\)
从图中还可以看出,先沿 \(x\) 遍历,然后跳到下一列 \(y\)。
代码(核心部分):
for (int x = 0; x <= n; x++) {for (int y = 0; y <= n; y++) {if (x == 0) {dp[x][y] = 1;} else if (y == 0) {dp[x][y] = dp[x - 1][y + 1];} else {dp[x][y] = dp[x][y - 1] + dp[x - 1][y + 1];}}}
[!important] 学到了什么?
对于这样一种问题:
给定初状态 \(P\),
可以进行 \(Op=\{...\}\) 种操作,每种操作会使当前状态转移到一个子状态。
求进行完所有操作后,可能的“操作路径”数。
那么我们用 DP 来解决问题,用反向推理的方法,其实 DP 转移方程很简单:
设计 DP 状态 \(dp(S)\)
(\(S\) 为状态,应该要包含各种在操作过程中会变化的量,比如要入栈的次数啊等等,写出来就是 \((x,y)\) 这样的式子)
\(dp(S)=\sum_i dp(S_i)\)
其中 \(S_i\) 表示从 \(S\) 可以进行到的子状态。