线性dp(时间复杂度N)

解题思路:
dp[i]=max(dp[i-1],v[i]+dp[i-2]) # v[i] 表示值&&i-2至少要隔开一个距离
注意事项:

参考代码:

list1=list(input())

temp=list(chr(i) for i in range(96,123))

dict1={}

for i,j in enumerate(temp[1:]):

    dict1[j]=i+1

dp=list(0 for i in range(len(list1)))

dp[0]=dict1[list1[0]]

for i in range(1,len(list1)):

    # 取和不取

    v1=dp[i-1]

    v2=dict1[list1[i]]

    if i>=2:

        v2+=dp[i-2]

    mmax=max(v1,v2)

    dp[i]=mmax

print(dp[-1])