递归，回溯，深度优先搜索
题目描述
有一叠扑克牌，每张牌介于1和10之间
有四种出牌方法：
单出1张
出2张对子
出五张顺子，如12345
出三连对子，如112233
给10个数，表示1-10每种牌有几张，问最少要多少次能出完
/m0_38065572/article/details/105019514
def dfs(l):if tuple(l) in memo:return memo[tuple(state)]if sum(l)==0:return 0else:res = float('inf')for i in range(10):if i<=5 and l[i]>=1 and l[i+1]>=1 and l[i+2]>=1 and l[i+3]>=1 and l[i+4]>=1:l[i:i+5]=[l[i+k]-1 for k in range(5)]res = min(res, dfs(l)+1)l[i:i+5]=[l[i+k]+1 for k in range(5)]memo[tuple(state)] = resif i<=7 and l[i]>=2 and l[i+1]>=2 and l[i+2]>=2:l[i:i+3]=[l[i+k]-1 for k in range(3)]res = min(res, dfs(l)+1)l[i:i+3]=[l[i+k]+1 for k in range(3)]memo[tuple(state)] = resif l[i]>=2:l[i]=l[i]-2res = min(res, dfs(l)+1)l[i]=l[i]+2memo[tuple(state)] = resif l[i]>=1:l[i]=l[i]-1res = min(res, dfs(l)+1)l[i]=l[i]+1memo[tuple(state)] = resreturn resdef input():l= '1 1 2 2 2 1 1 0 0 0'return lmemo={}state= list(map(int,input().split()))print(state)print(dfs(state))
题目描述
首先定义上升字符串，对于任意的0<i<len(s)0<i<len(s)0<i<len(s)，s[i]≥s[i−1],比如aaa，abc是，acbd不是
给n个上升字符串，选择任意个拼起来，问能拼出来的最长上升字符串长度
/m0_38065572/article/details/105019514
这个题目很类似于一个经典的题目，课表安排的问题，课表安排的问题可以使用动态规划，或贪心。
到j的最长长度是dpj
到j-1的最长长度dpj-1 和 到i的最长长度dpi+Sij 中间 较大的一个
动态规划问题可以用递归回溯，也可以记录每一步状态（这道题目中状态是以字符‘j’结尾的最长长度）
def longestAscString(strs:List[str])-> int:strs=sorted(strs,key=lambda x:(x[-1],x[0])) #尾字符升序,第二关键字为首字符升dp=[0]*26 #记录以字符j结尾的最长长度res=0# 记录全局最优last=0for string in strs:begin=ord(string[0])-ord('a')end=ord(string[-1])-ord('a')for i in range(last,end): # 没有这些字符结尾的最长长度，使用前面的最长长度更新dp[i+1]=dp[last]dp[end]=max(dp[end],dp[begin]+len(string))#dp递推公式，从记录的上一步全局最有值，推到下一步全局最优res=max(res,dp[end])last=endreturn resa=["bcdefhijk","bcd","aaa","eeeefghhh","zzzz",]b=['abc','hpq','qrt','jklmnopqr','abcjklmnopqr',]c=['abcd','deft','efghmnt','defghjkl','abcddefghjkl',]print(longestAscString(c))
打牌博弈 dfs深度优先遍历搜索 排课表 拓扑排序 升序字符串 动态规划 剑指offer编程题整理 leetcode每日算法题
如果觉得《打牌博弈 dfs深度优先遍历搜索 排课表 拓扑排序 升序字符串 动态规划 剑指offer》对你有帮助，请点赞、收藏，并留下你的观点哦！
