第四题贴个代码，做法没问题，python没有gc所以一直内存超限。。优化了很久把dp的dict改成反复清空的一维list还是不行，十分郁闷。。 其实思路跟leetcode813.最大平均值和的分组差不多，就是把平均数换成了类别数 import sys def largestScore(A: list, K: int) -> float: n = len(A) count = {} # 先计算各个段的场次数方便后面调用 for i in range(n): now = {A[i]} count[i, i+1] = 1 for j in range(i+1, n): now.add(A[j]) count[i, j+1] = len(now) dp = {(1, i): count[0, i] for i in range(1, n+1)} # dp[k, i] 前i个数分成k组的最大分数 for i in range(2, n+1): for j in range(i, n+1): _max = dp[i-1, j-1] + 1 for k in range(i-1, j-1): _max = max(_max, dp[i-1, k] + count[k, j]) dp[i, j] = _max return dp[K, n] _, K = map(int, sys.stdin.readline().strip().split(' ')) A = list(map(int, sys.stdin.readline().strip().split(' '))) print(largestScore(A, K))