PHP数组子序列数量计算方法

本文深入解析了PHP中高效计算数组子序列出现次数的核心算法，重点介绍基于动态规划的一维优化解法——通过倒序更新状态数组，在O(n×m)时间复杂度内精准统计保持相对顺序但不必连续的子序列方案数（如[1,2,2,3]中[1,2,3]出现2次），同时兼顾递归记忆化实现便于理解，并详述重复元素处理、边界条件判断及类型统一等实战细节，为PHP开发者提供可直接落地的高性能解决方案。

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

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~