AcWing--松散子序列--＞dp，状态机

?两种做法：

5406. 松散子序列 - AcWing题库（python)

二维:

# 输入
s = list(input())
n = len(s) + 1
s = [0] + s
# 求价值之和最大值
# dp算法

# 状态表示 ?f(i,0) 不选 ?前一个字符 可选 可不选
# f(i,1) 选 前一个不选的+的当前价值

# 属性 最大价值
#?
# 创建dp数组

# 创建二维dp数组
dp = list([0] * 2 for _ in range(n))
# print(dp)
# [[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]]
#?
for i in range(1, n):
? ? dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
? ? dp[i][1] = dp[i - 1][0] + ord(s[i]) - ord("a") + 1

print(max(dp[n-1][0], dp[n-1][1]))
?

?优化一维：

?s = [0]+list(input())
n=len(s)
# [0, 'a', 'z', 'a', 'a', 'z', 'a', 'z']
# 8
# 创建dp数组
dp=[0]*(n)
dp[1]=ord(s[1])-ord("a")+1
for i in range (2,n):
? ? dp[i]=max(dp[i-1],dp[i-2]+ord(s[i])-ord("a")+1)
print(dp[n-1])