如何统计字符串数组按首尾同值规则拆分的分组方案数

这道题适合用动态规划求解，具体逻辑如下：

• 定义状态dp[i][j]：表示数组前i个元素（即下标从0到i-1的元素），拆分为j个符合要求的分组的总方案数
• 边界条件：dp[0][0] = 1，表示0个元素拆分为0组的方案数为1，作为基础递推起点
• 转移逻辑：
  1. 对每个分组数j，遍历所有可能的前i个元素的情况，由于j个分组最少需要2*j个元素，因此i < 2*j时dp[i][j]直接为0，无需计算
  2. 对每个合法的i，遍历所有可能的分组切割点k：k是前j-1组的结束位置，要求k至少为2*(j-1)（j-1组最少需要的元素数），且i - k >=2（当前第j组最少有2个元素）
  3. 验证从k到i-1的子数组是否符合要求：即x[k].equals(x[i-1])，如果符合则把dp[k][j-1]的数值累加到dp[i][j]中
• 最终结果就是dp[x.length][N]

public class GroupSplit {
    public static int groupCount(String[] x, int N) {
        int len = x.length;
        // 合法性校验：N个组最少需要2*N个元素，不符合要求直接返回0
        if (len < 2 * N || N <= 0) {
            return 0;
        }
        int[][] dp = new int[len + 1][N + 1];
        dp[0][0] = 1;
        // 遍历分组数
        for (int j = 1; j <= N; j++) {
            // j个组最少需要2*j个元素，i从2*j开始遍历
            for (int i = 2 * j; i <= len; i++) {
                // k为前j-1组的结束下标
                for (int k = 2 * (j - 1); k <= i - 2; k++) {
                    // 验证当前分组首尾元素相同
                    if (x[k].equals(x[i - 1])) {
                        dp[i][j] += dp[k][j - 1];
                    }
                }
            }
        }
        return dp[len][N];
    }

    public static void main(String[] args) {
        String[] x = {"Boy", "Boy", "Girl", "Boy", "Girl", "Girl", "Boy", "Boy"};
        int N = 3;
        System.out.println(groupCount(x, N)); // 输出2，和示例结果一致
    }
}

• 时间复杂度：O(L²*N)，其中L是数组长度，三重循环的上限分别是N、L、L，实际因为有剪枝逻辑，运行耗时会低于理论上限
• 空间复杂度：O(L*N)，为dp数组的空间开销，如果数组长度很大，还可以用滚动数组优化到O(L)的空间复杂度

内容的提问来源于stack exchange，提问作者NOOBatProgramming