解题思路:
代码前的思考:由于每一项的值都大于0,所以我们要尽可能的多选,将问题转换成:给定一个序列,要求不能选取相邻的元素,问能获得的最大价值是多少?
1、分别记录每个点取或不取所形成的价值
2、取的话就等于上一项不取加上本项的价值
3、不取的话等于上一项取或者不取中的最大值
注意事项:
dp[i][0]:不取第i项的价值(i从0开始)
dp[i][1]:取第i项的价值
答案是最后一项取或不取的最大值
温馨提示,这是一类有代表性的问题,具体可以参考Leetcode上的打家劫舍问题系列
参考代码:
def get(c): #获得字符的价值 return ord(c)-ord('a')+1 s=input() n=len(s) dp=[[0,0] for i in range(n)] dp[0][1]=get(s[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]+get(s[i]) # 取这一项的话上一项只能不取了 print(max(dp[-1][0],dp[-1][1]))
0.0分
29 人评分
点我有惊喜!你懂得!浏览:1670 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:1204 |
蓝桥杯历届试题-九宫重排 (C++代码)浏览:2783 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:411 |
printf基础练习2 (C语言代码)浏览:305 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:1068 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:699 |
字符串的输入输出处理 (C语言代码)浏览:989 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:463 |
A+B for Input-Output Practice (I) (C语言代码)浏览:429 |