描述

给定一个字符串 S ，定义三种有价值的字符串： A = "nico" ，B = "niconi" , C = "niconiconi"
其中，字符串 A 的价值为 a， 字符串 B 的价值为 b，字符串 C 的价值为 c
她拿到了一个长度为 n 的字符串，你需要在其中找到一些有价值的子串 (指字符串中连续的一段)，并统计价值之和的最大值。
注：已被计算价值过的字符不能重复计算价值！如 "niconico" 要么当作 "nico" + "nico" 计 2a 分，要么当作 "niconi" + "co" 计 b 分（其中 "co" 不计分）。

示例1

输入：
19 1 2 5
niconiconiconiconi~

输出：
7

说明：
"niconi"co"niconiconi"~
故为2+5=7分

示例2

输入：
6 1 2 5
nocole

输出：
0

思路

开门见山了，这道题可以采用动态规划的方式来解决。
首先，状态转移方程是：

dp[i] = Math.max(dp[i], Math.max(dp[i-3]+a, dp[i-5]+b, dp[i-9]+c))

其实也不难理解，就是没到一个地方，就判断一下符合 a、b、c 那个，在取最大的就行，然后用 dp 数组记录一下，注意：dp 数组是递增或平行的。

AC 代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String line = sc.nextLine();
        String[] split = line.split(" ");
        int n = Integer.parseInt(split[0]);
        int a = Integer.parseInt(split[1]);
        int b = Integer.parseInt(split[2]);
        int c = Integer.parseInt(split[3]);
        String line1 = sc.nextLine();
        long res = run1(n, a, b, c, line1);
        System.out.println(res);
    }


    public static long run1(int n, int a, int b, int c, String s) {
        if (s == null || s.length() < 4) {
            return 0;
        }

        long[] dp = new long[n];

        for (int i = 3; i < n; i ++) {
            dp[i] = dp[i - 1];
            if (i >= 3 && s.substring(i- 3, i + 1).equals("nico")) {
                dp[i] = Math.max(dp[i], dp[i - 3] + a);
            }
            if (i >=5 && s.substring(i - 5, i + 1).equals("niconi")) {
                dp[i] = Math.max(dp[i], dp[i - 5] + b);
            }
            if (i >= 9 && s.substring(i - 9, i + 1).equals("niconiconi")) {
                dp[i] = Math.max(dp[i], dp[i - 9] + c);
            }
        }

        return dp[n - 1];
    }
}

• 时间复杂度：O(N), N 为字符串长度，需要遍历一遍
• 空间复杂度：O(N), N 为字符串长度，需要创建 dp 数组