解题思路

本题属于典型的“划分型动态规划”。设字符串为 s[0..n-1]，我们用二维 DP 来描述“前缀被切成若干段且每段为回文”的方案数：

• 定义 dp[i][j]：表示把前 i 个字符（即 s[0..i-1]）切分成恰好 j 段回文子串的方案数。

• 初始条件：dp[0][0] = 1（空串切成 0 段只有 1 种方式），其余为 0。

• 状态转移：枚举最后一段的起点 t（最后一段为 s[t..i-1]，其中 j-1 ≤ t ≤ i-1） 若 s[t..i-1] 是回文，则有

  dp[i][j] += dp[t][j-1]
  

• 最终答案：dp[n][k]。

复杂度分析

• 时间复杂度：三层循环（i、j、t）叠加上每次 O(长度) 的回文检查，整体 O(n^3)
• 空间复杂度：O(nk) 存储 DP 表，最坏 O(n^2)。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意：将字符串 s 切分成恰好 k 个非空连续回文子串的方案数
# 要求：O(n^3)，不做回文预处理

import sys

def is_pal(s, l, r):
    """现场检查 s[l..r] 是否为回文，双指针 O(r-l+1)"""
    while l < r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True

def count_partitions(s, k):
    n = len(s)
    # dp[i][j]: 前 i 个字符切成 j 段回文的方案数
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # 空串切成 0 段

    for i in range(1, n + 1):                     # 前缀长度
        up = min(i, k)
        for j in range(1, up + 1):                # 段数
            # 最后一段为 s[t..i-1]，t 至少为 j-1（每段至少1个字符）
            for t in range(j - 1, i):
                if is_pal(s, t, i - 1):
                    dp[i][j] += dp[t][j - 1]
    return dp[n][k]

def main():
    data = sys.stdin.read().strip().splitlines()
    s = data[0].strip()
    k = int(data[1].strip())
    print(count_partitions(s, k))

if __name__ == "__main__":
    main()

Java

// 题意：将字符串 s 切分成恰好 k 个非空连续回文子串的方案数
// 要求：O(n^3)，不做回文预处理
import java.util.*;

public class Main {
    // 现场判断回文：检查 chars[l..r]
    static boolean isPal(char[] chars, int l, int r) {
        while (l < r) {
            if (chars[l] != chars[r]) return false;
            l++; r--;
        }
        return true;
    }

    static long countPartitions(String s, int k) {
        int n = s.length();
        long[][] dp = new long[n + 1][k + 1];
        dp[0][0] = 1; // 空串切成0段

        char[] cs = s.toCharArray();
        for (int i = 1; i <= n; i++) {                // 前缀长度
            int up = Math.min(i, k);
            for (int j = 1; j <= up; j++) {           // 段数
                // 最后一段为 [t..i-1]，t 至少为 j-1
                for (int t = j - 1; t <= i - 1; t++) {
                    if (isPal(cs, t, i - 1)) {
                        dp[i][j] += dp[t][j - 1];
                    }
                }
            }
        }
        return dp[n][k];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine().trim();
        int k = Integer.parseInt(sc.nextLine().trim());
        System.out.println(countPartitions(s, k));
        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 现场判断回文：检查 s[l..r]（闭区间）
static bool isPal(const string &s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) return false;
        ++l; --r;
    }
    return true;
}

static long long countPartitions(const string &s, int k) {
    int n = (int)s.size();
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
    dp[0][0] = 1; // 空串切成0段

    for (int i = 1; i <= n; ++i) {               // 前缀长度
        int up = min(i, k);
        for (int j = 1; j <= up; ++j) {          // 段数
            // 最后一段为 [t..i-1]，t 至少为 j-1
            for (int t = j - 1; t <= i - 1; ++t) {
                if (isPal(s, t, i - 1)) {
                    dp[i][j] += dp[t][j - 1];
                }
            }
        }
    }
    return dp[n][k];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    int k;
    cin >> s >> k;
    cout << countPartitions(s, k) << "\n";
    return 0;
}

题面描述

给定一个只包含小写字母的字符串 $s$（长度为 $n$）和一个整数 $k$。请将 $s$ 切分成恰好 $k$ 个非空且连续的子串，并使得每个子串都是回文串。求满足条件的切分方案数；若无解则输出 0。 切分的位置不同视为不同方案。

输入输出

输入： 第一行一个字符串 $s$。 第二行一个整数 $k$。

输出： 输出一个整数，表示将 $s$ 切分成 $k$ 个回文子串的方案数。

数据范围

• $1 \le n=|s| \le 60$
• $1 \le k \le n$
• 字符仅由小写字母组成

样例

输入

aab
2

输出

1

说明 只存在切分 aa|b。

输入

aaaa
3

输出

3

说明 可行切分为 a|a|aa、a|aa|a、aa|a|a。