题目重点：OA 题目给等长 words、target、列下标严格递增和 mod 1e9+7；用列频次与一维逆序 DP 求方法数，并验证示例。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 每次从某一列选择一行的字符，下一目标字符必须来自更靠后的列；同行可跨列重复使用，题目只限制列下标。
- 不同选择路径按每列选中的 word 行号区分，即同一列某字符出现 count 次就产生 count 倍方法数。words 等长；空 target 有 1 种空选法。
解题路线
- 预处理或逐列统计当前列每个字符出现次数 count[col][char]。
- 令 dp[j] 为处理过当前列后形成 target 前 j 个字符的方法数，初始 dp[0]=1。处理列 col 时，从大的 j 到小的 j 更新 dp[j]+=dp[j−1]×count[col][target[j−1]]。
- 倒序更新防止同一列被用于 target 的多个位置；每次取模。若 target 长度大于列数，答案自然为 0。
- 随机小规模用递归选择“跳过当前列”或“选此列某行字符”的穷举计数比较 10,000 组，题目 val 示例算得 4。
手动走一遍
words=['valya','vidhi','lyglb']、target='val'。对每一列统计 a/v/l 的出现次数，再按列推进 dp；最终 dp[3]=4。相同列即使有多个可选行，也只能为 target 的一个位置贡献，不能在一个列里连取两字。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Count target constructions using strictly increasing word-column indices."""
from collections import Counter
MOD = 1_000_000_007
def count_formations(words: list[str], target: str) -> int:
if not words:
return int(target == "")
width = len(words[0])
if any(len(word) != width for word in words):
raise ValueError("word lengths must match")
dp = [0] * (len(target) + 1)
dp[0] = 1
for column in range(width):
counts = Counter(word[column] for word in words)
for length in range(min(len(target), column + 1), 0, -1):
dp[length] = (dp[length] + dp[length - 1] * counts[target[length - 1]]) % MOD
return dp[len(target)]
复杂度
W 个 word、每词 M 列、target 长 T；逐列构建 Counter 需 O(WM)，DP O(MT)，总 O(WM+MT) 时间、O(T+Σ) 工作空间，Σ 为单列字符种类数。若预存所有列频次则空间 O(MΣ)。
易错点与追问
容易失分的边界
- 正序更新一维 dp，使同一列被重复使用。
- 把 words 看作整词拼接，不按列选择。
- 同字符在一列出现多次只算 1 种，漏掉不同 word 行选择。
- target 长度超过 M 时仍枚举无意义状态。
- 忘记在乘法与加法后取模。
继续深挖
- 若列序允许相同或不递增，状态转移会如何变化？
- 如果同一 word 行也不能重复使用，为什么一维 DP 不够？
- 大量不同 target 查询共享同一 words，哪些预计算可复用？
