PHP数组子序列数量计算解析

本文深入解析了PHP中高效统计数组子序列出现次数的核心算法，重点讲解了动态规划这一最优解法——通过二维DP状态定义与巧妙的一维空间优化（倒序更新），在O(n×m)时间内精准计算保持相对顺序但不必连续的子序列匹配方案数；同时辅以递归+记忆化的直观实现帮助理解逻辑，并贴心提醒重复元素处理、空序列边界、类型一致性等实战细节，配以清晰代码示例，让开发者既能掌握原理又能即学即用。

PHP 中统计数组中某个子序列（subsequence）出现次数，关键在于理解“子序列”不等于“子串”：元素不必连续，但必须保持原有相对顺序。常见需求如：给定数组 [1,2,2,3] 和目标子序列 [1,2,3]，求其作为子序列在原数组中出现的方案数（结果为 2）。

动态规划解法（推荐，时间 O(n×m)，空间可优化）

设 $arr 长度为 n，子序列 $seq 长度为 m。定义 $dp[i][j] 表示用 $arr[0..i-1] 匹配 $seq[0..j-1] 的方案数。

• 初始化：$dp[i][0] = 1（空子序列总能被任意前缀匹配 1 次）；$dp[0][j] = 0（非空子序列无法用空数组匹配）
• 状态转移：
  若 $arr[i-1] == $seq[j-1]，则 $dp[i][j] = $dp[i-1][j-1] + $dp[i-1][j]（选当前元素或不选）；
  否则 $dp[i][j] = $dp[i-1][j]（只能跳过当前元素）
• 空间优化：因每行只依赖上一行，可用一维数组 $dp[j] 倒序更新（从 j = m 到 1），避免覆盖

递归 + 记忆化（适合理解逻辑）

用函数 countSubseq($i, $j) 表示从 $arr[$i] 开始匹配 $seq[$j] 起的子序列数：

• 边界：若 $j == count($seq)，返回 1（已完全匹配）；若 $i == count($arr) 且 $j ，返回 0
• 若 $arr[$i] == $seq[$j]，可选或不选：countSubseq($i+1, $j+1) + countSubseq($i+1, $j)
• 否则只能跳过：countSubseq($i+1, $j)
• 用二维数组缓存 memo[$i][$j] 防止重复计算

处理重复元素与边界情况

算法天然支持重复值（如 [2,2,2] 中子序列 [2,2] 出现 3 次），无需额外去重。但需注意：

• 若 $seq 为空数组，按约定返回 1
• 若 $seq 长度大于 $arr，直接返回 0
• 数值类型需一致（如字符串 "2" 与整数 2 不等），建议提前用 array_map('strval', ...) 或 array_map('intval', ...) 统一

PHP 实现示例（一维 DP）

$arr = [1,2,2,3];
$seq = [1,2,3];
$n = count($arr);
$m = count($seq);

$dp = array_fill(0, $m + 1, 0);
$dp[0] = 1; // 空子序列

for ($i = 0; $i = 1; $j--) {
        if ($arr[$i] == $seq[$j-1]) {
            $dp[$j] += $dp[$j-1];
        }
    }
}
echo $dp[$m]; // 输出 2

到这里，我们也就讲完了《PHP数组子序列数量计算解析》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！