P1044 [NOIP 2003 普及组] 栈

难度	算法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$ 可以进行到的子状态。