题目来源以及题解：
https://www.nowcoder.com/discuss/387100?type=0&order=0&pos=52&page=1
https://www.nowcoder.com/discuss/387726?type=post&order=time&pos=&page=1
https://www.nowcoder.com/discuss/387802?type=1
第二题：
作者：牛客585071975号
链接：https://www.nowcoder.com/discuss/387802?type=1
来源：牛客网
小明在学旋律，每段旋律都可以用字符串来表示，并且旋律的每个字符的ASCALL码递增的比如以下4段旋律 ：aaa bcd bcdef zzz 现在就是要求，小明能够吧这些旋律拼接起来组成最长的旋律。比如上述例子输出 11 最长的旋律为 aaabcdefzzz `
思路（一堆废话预警）（看了大佬们的题解才看懂）：
先用一个列表保存输入的旋律musicList（比如['aaa', 'bcd', 'bcdef', 'zzzz']）
然后利用动态规划，dp[i]表示当有第i段旋律时，拼接起来组成最长的旋律长度
比如dp[2]表示有'aaa', 'bcd', 'bcdef'这三段旋律时，拼接起来组成最长的旋律长度为8（aaabcdef）
问题来了， 如何求dp[i]
- 首先要把musicList按照ASCII码递增排序 musicList.sort()
- dp[0] 就是列表中第一段旋律的长度（此时只有一段旋律）
- 当i>.0， 判断musicList[i]这段旋律能否与它前面的旋律拼接起来
比如i=2，要判断bcdef能否拼接在aaa后面、能否拼接在bcd后面。（让bcdef去与bcdef前面的旋律aaa、bcd都试探一下）- 如果能拼接在aaa后面，拼接后的长度为dp[0] + len(musicList[i])
- 如果能拼接在bcd后面，拼接后的长度为dp[1] + len(musicList[i])
- 判断是否能拼接：musicList[i]的首个字符ASCII码要≥ 待拼接旋律最后一个字符ASCII码
题解：https://www.nowcoder.com/discuss/387726?type=post&order=time&pos=&page=1
或者是从前往后想，上面的第三步：
- 当i>.0， 判断musicList[i]这段旋律能否与它后面的旋律拼接起来
对于 一段旋律i， 遍历它后面的旋律j=i+1,….，看后面的旋律能否加在这段旋律后面
比如 bcd , 判断bcdef能否加在bcd后面、判断zzzz能否加在bcd后面
即：dp[j] = 已拼接好bcd的旋律的最长长度+ musicList[j]的长度
大佬题解地址：https://www.nowcoder.com/discuss/387100?type=0&order=0&pos=52&page=1
照着大佬的题解，补充了读取输入，下面是完整的程序：
关键函数是大佬写的我只是照着写了一遍，大佬本来的代码在上面
import sys
class Solution:
def getMusic(self,musicList):
if not musicList: return 0
musicList.sort() #把旋律们按照升序排序
dp = [0 for _ in range (len(musicList))]
dp[0] = len(musicList[0])
for i in range(len(musicList)):
for j in range(i+1,len(musicList)):
if musicList[j][0] >= musicList[i][-1]:
dp[j] = dp[i] + len(musicList[j])
return dp[-1]
if __name__ == "__main__":
solution = Solution()
try:
musicList = []
while True:
m = sys.stdin.readline().strip()
if m == '':
break
m = list(m.split())
musicList.extend(m) #存成一个一维list
print(musicList)
except:
pass
res = solution.getMusic(musicList)
print(res)
第一题：
题目来源 https://www.nowcoder.com/discuss/387802?type=1
有一叠扑克牌，每张牌介于1和10之间
有四种出牌方法：
单出1张
出2张对子
出五张顺子，如12345
出三连对子，如112233
给10个数，表示1-10每种牌有几张，问最少要多少次能出完
明天接着看今天看不动了
