aiaiask.com©

开花即结果 提问即答案

计算首尾字符相同子序列的数量:Java代码实现与模运算优化
原始问题:

计算首尾字符相同子序列的数量:Java代码实现与模运算优化

以下是使用Java代码实现的解决方案:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        int result = countSubsequences(str);
        System.out.println(result);
    }

    public static int countSubsequences(String str) {
        int mod = 998244353;
        int[] dp = new int[26];
        int[] prev = new int[26];
        int n = str.length();
        int result = 0;

        for (int i = 0; i < n; i++) {
            int index = str.charAt(i) - 'a';
            dp[index] = (2 * prev[index] + 1) % mod;
            prev[index] = (prev[index] + dp[index]) % mod;
        }

        for (int i = 0; i < 26; i++) {
            result = (result + dp[i]) % mod;
        }

        return result;
    }
}

这段代码中,我们使用动态规划的思想来解决问题。我们定义两个数组dp和prev,分别用来记录当前字符结尾的子序列数量和上一个字符结尾的子序列数量。

我们遍历字符串中的每个字符,对于每个字符,我们计算以该字符结尾的子序列数量。具体计算方法如下:

  1. 首先,我们根据当前字符的ASCII码值计算出对应的索引index。
  2. 然后,我们更新dp[index]的值,根据上一个字符结尾的子序列数量prev[index]计算得到。具体计算方法为dp[index] = (2 * prev[index] + 1) % mod,其中mod为取模的值。
  3. 最后,我们更新prev[index]的值,将其更新为prev[index] + dp[index]。

最后,我们遍历dp数组,将所有元素相加并对mod取模,得到满足条件的子序列的数量。

注意:由于题目要求对结果取模,所以在计算过程中需要注意取模的位置,以避免整数溢出。

计算首尾字符相同子序列的数量:Java代码实现与模运算优化
https://www.aiaiask.com/ask/45736.html
AI / 模型iFLYTEK
时间 / DATESeptember 2, 2023, 3:13 PM
语言zh-CN
IP / 区域华盛顿州Seattle