18-动规-子序列中的 k 种字母（中等）

题目

来源

28. 子序列中的 k 种字母（第一期模拟笔试）

思路

基本分析 

子序列的定义

子序列是从原序列中选取部分元素，同时保持这些元素在原序列中的相对顺序所形成的新序列。也就是说，子序列中的元素不需要在原序列中连续出现，但它们的先后顺序必须和原序列一致。例如，对于字符串 "abc"，它的子序列有 "","a","b","c","ab","ac","bc","abc"。

输入要求

• 第一行输入包含两个整数 n 和 k，其中 n 表示字符串的长度（范围是 1 ≤ n ≤ 1000），k 表示符合要求的子序列中需要包含的不同字母的种类数（范围是 1 ≤ k ≤ 26）。
• 第二行输入是一个长度为 n 的仅由小写字母组成的字符串。

输出要求

需要输出一个整数，表示该字符串中恰好包含 k 种不同字母的子序列的数量。由于结果可能非常大，需要将答案对 10^9 + 7 取模后再输出。

动态规划思路分析

为什么使用动态规划

动态规划适用于解决具有重叠子问题和最优子结构性质的问题。在本题中，要计算包含 k 种字母的子序列数量，可以通过逐步计算包含较少字母种类的子序列数量，进而推导出包含更多字母种类的子序列数量，符合动态规划的应用场景。

动态规划的具体思路

1. 定义状态：
   定义 dp[j] 表示恰好包含 j 种不同字母的子序列的数量。初始时，dp[0] = 1，因为空序列可以看作是包含 0 种字母的子序列。

2. 状态转移：
   对于字符串中的每个字母，我们考虑它对 dp 数组的影响。假设当前处理到第 i 个字母（这里 i 是字母在字母表中的索引，范围是 0 到 25），其出现的次数为 cnt[i]。

   • 我们先计算出当前字母的非空子序列的数量 b。
   • 然后从 k 到 1 倒序遍历 dp 数组，对于每个 j，更新 dp[j] 的值。具体来说，dp[j] 要加上 dp[j - 1] * b，这是因为我们可以将当前字母的非空子序列添加到已经包含 j - 1 种字母的子序列中，从而得到包含 j 种字母的新子序列。

3. 最终结果：
   经过对所有字母的处理后，dp[k] 就表示恰好包含 k 种不同字母的子序列的数量。

为什么 pow(2, cnt[i], mod) 表示当前字母的所有子序列的数量（包括空序列）

假设一个字母在字符串中出现了 cnt[i] 次。对于这个字母的每一次出现，在构成子序列时，我们都有两种选择：要么选择该次出现的字母加入子序列，要么不选择。

例如，当一个字母出现 1 次时，有 2 种选择：选这个字母（子序列为该字母本身）或者不选（子序列为空）。

当一个字母出现 2 次时，对于第一次出现有 2 种选择（选或不选），对于第二次出现同样有 2 种选择。根据乘法原理，总的选择方案数就是 2 * 2 = 2^2 种，分别是 "","a","a","aa"（这里假设字母是"a"）。

以此类推，当一个字母出现 cnt[i] 次时，总的选择方案数就是 2 * 2 * ... * 2 = 2^cnt[i] 种，这就表示了该字母的所有子序列的数量，包括空序列。

在代码中，使用 pow(2, cnt[i], mod) 是为了避免在计算 2^cnt[i] 时出现数值溢出的问题，通过取模运算保证结果在合理范围内。同时，为了得到非空子序列的数量，我们需要将总的子序列数量减去 1（即减去空序列这一种情况），所以有 b = (pow(2, cnt[i], mod) - 1) % mod。

pow(2, cnt[i], mod) 

pow(2, cnt[i], mod) 是 Python 内置函数 pow() 的一个应用，它的作用是高效地计算 2 的 cnt[i] 次幂并对 mod 取模

为什么要从 k 到 1 倒序遍历 dp 数组？

在这个动态规划问题里，从 k 到 1 倒序遍历 dp 数组是为了避免在更新 dp 数组时出现重复计算的问题，确保每个状态在更新时使用的是上一轮循环的旧值，下面详细解释其中的原因。

动态规划状态转移方程

在本题的动态规划中，状态转移方程为 dp[j] += dp[j - 1] * b，这里的 dp[j] 表示恰好包含 j 种不同字母的子序列的数量，b 是当前字母的非空子序列的数量。此方程的含义是，把当前字母的非空子序列添加到已经包含 j - 1 种字母的子序列里，从而得到包含 j 种字母的新子序列。

为什么最外层循环是# 遍历每个字母 for i in range(26)

在这个动态规划问题里，最外层循环 for i in range(26) 的作用是遍历 26 个小写英文字母，进而逐个考虑每个字母对最终结果的影响，下面详细解释这样做的原因。

问题本质与字母的影响

本题的目标是计算给定字符串中恰好包含 k 种不同字母的子序列的数量。在动态规划的过程中，我们需要逐步考虑每种字母在构成子序列时所起到的作用。由于字符串仅由小写字母组成，小写字母共有 26 个，所以要对这 26 个字母依次进行遍历。

代码

Python 

# 读取输入的字符串长度 n 和所需的字母种类数 k
n, k = map(int, input().split())

# 创建一个长度为 26 的数组 cnt，用于统计每个字母的出现次数
cnt = [0] * 26

# 创建一个长度为 k + 1 的数组 dp，dp[j] 表示恰好包含 j 种字母的子序列的数量
# 初始时，dp[0] = 1，表示空序列恰好包含 0 种字母
dp = [0] * (k + 1)
dp[0] = 1

# 读取输入的字符串
for c in input():
    # 统计每个字母的出现次数
    cnt[ord(c) - ord('a')] += 1

# 定义取模的常量
mod = int(1e9 + 7)

# 遍历每个字母
for i in range(26):
    # 计算当前字母的非空子序列的数量
    # pow(2, cnt[i], mod) 表示当前字母的所有子序列的数量（包括空序列）
    # 减去 1 后得到非空子序列的数量
    b = (pow(2, cnt[i], mod) - 1) % mod
    # 从后往前更新 dp 数组，避免重复计算
    for j in range(k, 0, -1):
        # 状态转移方程：dp[j] 加上 dp[j - 1] 乘以当前字母的非空子序列的数量
        dp[j] += dp[j - 1] * b
        # 对结果取模，避免溢出
        dp[j] %= mod

# 输出恰好包含 k 种字母的子序列的数量
print(dp[k])

C++ 

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

const int N = 1010;
const int MOD = 1e9 + 7;
int dp[N], cnt[26];

// 快速幂函数，计算 base 的 exp 次幂对 mod 取模的结果
long long fastPow(long long base, long long exp, long long mod) {
  long long result = 1;
  base = base % mod;
  while (exp > 0) {
    if (exp % 2 == 1) {
      result = (result * base) % mod;
    }
    base = (base * base) % mod;
    exp = exp / 2;
  }
  return result;
}

int main() {
  int n, k;
  cin >> n >> k;
  // 读取字符串并统计每个字母的出现次数
  for (int i = 0; i < n; i++) {
    char a;
    cin >> a;
    cnt[a - 'a']++;
  }
  // 初始化 dp 数组，空序列包含 0 种字母
  dp[0] = 1;
  // 遍历每个字母
  for (int i = 0; i < 26; i++) {
    // 计算当前字母的非空子序列的数量
    int b = (fastPow(2, cnt[i], MOD) - 1 + MOD) % MOD;
    // 从后往前更新 dp 数组
    for (int j = k; j > 0; j--) {
      // 状态转移方程，更新 dp[j] 并取模
      dp[j] = (dp[j] + 1LL * dp[j - 1] * b) % MOD;
    }
  }
  // 输出结果
  cout << dp[k] << endl;
  return 0;
}