深入浅出杨表 (Young Tableau)：从组合数学到算法降维打击
在普通算法视角下，求解最长上升子序列 (LIS) 需要用到动态规划。但如果题目要求我们统计 **“所有可能排列中，LIS 长度的期望 / 总和”**，动态规划就会面临状态爆炸的绝境。
此时，我们需要引入组合数学中的核武器——杨表 (Young Tableau)。它建立了一座连接“排列”与“二维图形”的桥梁。
一、 核心概念：杨图与标准杨表
1. 整数划分与杨图 (Young Diagram)
假设有一个正整数 n ，我们将它拆分成若干个正整数的和： \lambda_1 + \lambda_2 + \cdots + \lambda_k = n ，并且要求 \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k > 0 。这就叫 n 的一个整数划分，记作 \lambda \vdash n 。
我们可以把这种划分画成一个“左对齐、顶对齐”的二维方格图，这就是杨图。例如 n = 5 ，划分 (3,2) 对应的杨图如下：
┌─┬─┬─┐
│ │ │ │ <-- 第 1 行有 3 个格子 (λ₁ = 3)
├─┼─┼─┘
│ │ │ <-- 第 2 行有 2 个格子 (λ₂ = 2)
└─┴─┘
2. 标准杨表 (Standard Young Tableau, SYT)
如果在大小为 n 的杨图里，填入 1 到 n 这 n 个互不相同的数字，并且满足以下两个严格递增的条件：
- 每一行的数字从左到右严格递增。
- 每一列的数字从上到下严格递增。
这样的图形被称为标准杨表 (SYT)。对于上面的形状 (3,2) ，下面是一个合法的标准杨表：
┌─┬─┬─┐
│1│3│5│
├─┼─┼─┘
│2│4│
└─┴─┘
二、 核心定理一：钩长公式 (Hook Length Formula)
给定一个固定的形状 \lambda ，我们能填出多少种不同的标准杨表呢？设数量为 f^\lambda 。组合数学给出了一个极其优美的公式：钩长公式。
什么是“钩长 (Hook Length)”？ 对于杨表中的任意一个格子 (i,j) ，它的“钩子”包含：它自己、它正右方的所有格子、它正下方的所有格子。钩长 h(i,j) = 正右方的格子数 + 正下方的格子数 + 1。
以 (3,2) 为例，算出每个格子的钩长：
- 左上角格子
(0,0)：右边 2 个，下边 1 个。钩长 = 2 + 1 + 1 = 4 。 - 第1行中间
(0,1)：右边 1 个，下边 1 个。钩长 = 1 + 1 + 1 = 3 。
整个杨图的钩长矩阵如下：
[4, 3, 1]
[2, 1]
钩长公式：
计算实例： 对于 \lambda = (3,2) ， n = 5 ：分母 = 4 \times 3 \times 1 \times 2 \times 1 = 24 。分子 = 5! = 120 。 f^\lambda = 120 / 24 = 5 种。(这意味着形状为 (3,2) 的合法填法恰好有 5 种 )。
三、 核心定理二：RSK 对应 (降维打击的灵魂)
为什么我们要研究杨表？因为 Robinson-Schensted-Knuth (RSK) 对应定理 揭示了它与全排列的终极联系。
【RSK 定理】 任意一个长度为 n 的排列 \pi ，都与 一对 形状完全相同、大小为 n 的标准杨表 (P, Q) 存在一一对应的双射关系。
- P 表（插入表）：记录排列元素插入的值。
- Q 表（记录表）：记录元素插入的顺序（时间）。
由于是一一对应，这推导出了一个惊人的等式（排列总数等于所有形状的 P,Q 表组合数）：
★ 最神奇的性质：杨表与 LIS / LDS
如果你用排列 \pi 按照 RSK 算法构造出了对应的杨表形状 \lambda ，那么：
- \lambda_1 （第一行的长度） = 该排列的 最长上升子序列 (LIS) 长度！
- \lambda'_1 （第一列的长度） = 该排列的 最长下降子序列 (LDS) 长度！
四、 算法实战：它能解决什么问题？
典型问题：洛谷 P4484 - 求随机排列的最长上升子序列 (LIS) 期望
- 常规思路：状态压缩 DP。时间复杂度 O(n \cdot 2^n) ，空间 O(2^n) 。对于 n = 50 ，直接 TLE 和 MLE。
- 杨表思路： 我们要求所有排列的 LIS 长度之和，除以 n! 。根据 RSK 定理，LIS 长度等于 \lambda_1 。而产生形状 \lambda 的排列数量恰好是 (f^\lambda)^2 。
所以，LIS 总和 = \sum_{\lambda \vdash n} \lambda_1 \cdot (f^\lambda)^2 。
降维打击体现： 我们不再需要枚举 n! 种排列，也不需要遍历 2^n 种 DP 状态！我们只需要用 DFS 暴搜 n 的整数划分。当 n = 50 时，整数划分的总数只有 37338 种。对每一种划分，用钩长公式算出 f^\lambda ，乘以 \lambda_1 累加即可。时间复杂度直接降维至 O(p(n)) （ p(n) 是划分数），代码运行时间从无穷大骤降到 1 毫秒 内！
五、 总结与延申
- 杨氏矩阵 (Young Tableau in Leetcode)：在面试中，常有一道题“在每行递增、每列递增的二维矩阵中查找元素”。这个矩阵就是杨表。利用其右上角或左下角元素的单调性，可以实现 O(m+n) 的高效查找。
- 数学本质：杨表本质上是表示论（对称群的不可约表示）的可视化工具。在算法中，它完美地把序列的“单调性特征”（LIS/LDS）映射成了图形的“长宽特征”，从而将复杂的遍历问题转化为了数学公式求值问题。