目录
1. 题目：
给定一个仅含小写字母的字符串 s ，假设 s 的一个子序列 t 的第 i 个字符 对应了原字符串中的第 pi 个字符。我们定义 s 的一个松散子序列为：对于 i > 1 总是有 pi − pi−1 ≥ 2 。设一个子序列的价值为其包含的每个字符的价值之和 ( a ∼ z 分别为 1 ∼ 26 ) 。
求 s 的松散子序列中的最大价值。
输入格式
输入一行包含一个字符串 s 。
输出格式
输出一行包含一个整数表示答案。
样例输入
azaazaz
样例输出
78
2. 我的代码：
# 输入，字符变为值
s = list(input())
num_s = [0] + [ord(i) - 96 for i in s]
# 动态规划
dp = [0] * len(num_s)
dp[1] = num_s[1]
dp[2] = num_s[2]
for i in range(3, len(num_s)):
dp[i] = max(dp[i - 2], dp[i - 3]) + num_s[i]
print(max(dp[-1], dp[-2]))
这道题题目比较难读懂，慢慢读题，比如说：azaazaz的一个松散子序列可以是zzz，只要相隔为1个以上即可。可以仔细想一想，我们可以间隔1个，那么也可以间隔2个，那可以间隔3个吗。很明显再间隔大了就无意义了。因为间隔3个的时候正中间的数加上一定比不加上会大，所以，我们就推理得到了递推公式：dp[i] = max(dp[i - 2], dp[i - 3]) + num_s[i]。
由于递推公式需要用到前面3个元素的长度，所以，初始化最开始的3个元素。并且把0索引变为0，方便递推逻辑。
最后，要得到最后结果，必须是max(dp[-1], dp[-2])，因为有可能最后一个元素不加上的时候子序列更大。
小结：
关注我给大家分享更多有趣的知识，以下是个人公众号，提供 ||代码兼职|| ||代码问题求解||
添加我的公众号即可：