5.最长回文子串给定一个字符串s，找到s中最长的回文子串。您可以假设s的最大长度为1000。示例1：输入：“babad”输出：“bab”注意：“aba”也是一个有效答案。例2：输入："cbbd"输出："bb"思路1中心展开，即依次将每个字符作为回文串的中心字符，先向两边展开。这里需要注意的是，回文串需要分别作为奇数和偶数来考虑。deflongestPalindrome(s):ifnotsorlen(s)<2:returnsn=len(s)max_len=1start_idx=0#依次将每个字符作为回文串的中心，向两边扩充为iinrange(n):j=0#当回文串的长度为奇数时whilei-j>=0andi+jmax_len:max_len=2*j+1start_idx=i-jj+=1else:break#当回文长度为偶数时，j=0whilei-j-1>=0andi+jmax_len:max_len=2*(j+1)start_idx=i-j-1j+=1else:breakreturns[start_idx:start_idx+max_len]思路2动态规划deflongestPalindrome(s):n=len(s)dp=[[False]*nfor_inrange(n)]ans=""#枚举子串长度l+1forlinrange(n):#枚举起始位置i子串的结束位置，这样子串的结束位置可以通过j=i+lforiinrange(n):j=i+lifj>=len(s):breakifl==0:dp[i][j]=Trueelifl==1:dp[i][j]=(s[i]==s[j])否则:dp[i][j]=(dp[i+1][j-1]和s[i]==s[j])如果dp[i][j]和l+1>len(ans):ans=s[i:j+1]返回ans72。编辑距离给你两个词word1和word2，请计算将word1转换为word2所用的最少操作次数您可以对一个单词执行以下三种操作：插入一个字符删除一个字符替换一个字符示例1：输入：word1="horse",word2="ros"输出：3解释：horse->rorse(put'h'替换为'r')rorse->rose(删除'r')rose->ros(删除'e')示例2：输入：word1="intention",word2="execution"输出：5解释：intention->inention（删除't'）inention->enention（将'i'替换为'e'）enention->exention（将'n'替换为'x'）exention->exection（将'n'替换为'c''）exection->execution(insert'u')下面的格子表示word1和word2对应位置相互转换需要的步数，用二维数组dp表示$dp[i][j]$来表示word1的第i个位置改变到word2的第j个位置所需要的步数。数组dp的计算过程如下$$\begin{align}dp[i][j]&=dp[i-1][j-1],if\quadword1[i]=word2[j]\\dp[i][j]&=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1,其他\end{align}$$注意：第一行第一列要分开考虑，引入''，如下图。第一行表示''到word2的步数（也可以理解为word2到''的步数，一致），即插入的次数。第一列表示从word1到''的步数，即删除的次数。自底向上defminDistance(word1,word2):如果word1=='':返回len(word2)如果word2=='':返回len(word1)n1=len(word1)n2=len(word2)dp=[[0]*(n2+1)foriinrange(n1+1)]foriinrange(n1+1):dp[i][0]=iforiinrange(n2+1):dp[0][i]=iforiinrange(1,n1+1):forjinrange(1,n2+1):#状态转移方程ifword1[i-1]==word2[j-1]:dp[i][j]=dp[i-1][j-1]否则：dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1returndp[-1][-1]时间复杂度为$O(n^2)$,空间复杂度为$O(n^2)$自上而下,递归求解defminDistance(word1,word2):ifword1=='':returnlen(word2)ifword2=='':returnlen(word1)n1=len(word1)n2=len(word2)w1=[iforiinrange(n1+1)]w2=[iforiinrange(n2+1)]#如果不添加下面语句，会超时importfunctools#functools.lru_cache会保存中间结果保存，避免大量重复计算@functools.lru_cache(None)defhelper(m,n):如果m==1:返回w2[n-1]如果n==1:返回w1[m-1]如果word1[m-1]==word2[n-1]:returnhelper(m-1,n-1)else:returnmin(helper(m-1,n-1),helper(m-1,n),helper(m,n-1))+1returnhelper(n1+1,n2+1)198.房屋抢劫你是一名职业小偷，计划沿街盗窃房屋。每个房间都藏有一定数量的现金。影响盗窃的唯一限制是相邻的房屋。配备互联防盗系统，如果同一晚两间相邻房屋被盗贼闯入，系统会自动报警。给定一个非负整数数组，代表每个房子里存储的数量，计算你在一晚内可以偷走的最大数量而不触发警报。示例1：输入：[1,2,3,1]输出：4解释：偷房子#1（钱=1），然后偷房子#3（钱=3）。最大被盗金额=1+3=4。示例2：输入：[2,7,9,3,1]输出：12解释：偷1号房子（数量=2），偷3号房子（数量=9),然后偷5号房子(数量=1)。最大被盗数量=2+9+1=12。第$n$个数能窃取的最大值为$dp(n)$$dp(n)=max(dp(n-2)+nums(n),dp(n-1))$当前元素窃取：前一个不能被盗取，最大可以盗取的值等于$dp(n-2)+nums(n)$当前元素不盗取：前一个元素可以盗取的最大值，前一个元素是否被盗并不重要，最大可以被盗$dp(n-1)$可以被盗的最大值为$dp(n)=max(dp(n-2)+nums(n),dp(n-1))$defrob(nums):如果不是nums:返回0如果len(nums)==1:返回nums[0]如果len(nums)==2:返回max(nums[0],nums[1])rob_money=[nums[0],max(nums[0],nums[1])]n=len(nums)foriinrange(2,n):rob_money[0],rob_money[1]=rob_money[1],max(rob_money[0]+nums[i],rob_money[1])returnrob_money[1]213.HouseRobberyII你是一个专业的小偷，计划抢劫房子沿着街道，每个房间都藏有一定数量的现金。这个地方所有的房子都是排成一圈的，也就是说第一间房子和最后一间房子是紧挨着的。同时，相邻的房屋都配备了互联的防盗系统。如果同一晚两间相邻的房屋被小偷闯入，系统会自动报警。给定一个非负整数数组，代表每个房子里存储的数量，计算在不触发警报的情况下你可以偷走的最大数量。示例1：输入：[2,3,2]输出：3解释：你不能先偷房子1（钱=2），然后再偷房子3（钱=2），因为它们是相邻的。示例2：输入：[1,2,3,1]输出：4解释：你可以先偷房子1（数量=1），然后偷房子3（数量=3）。最大被盗数量=1+3=4。如果第一个元素被盗，最后一个元素就不能被盗。反之，如果最后一个被盗，第一个就不能被盗，总之不能同时被盗。然后我们可以计算出不偷第一个和不偷最后一个的最大值defrob(nums):ifnotnums:return0iflen(nums)==1:returnnums[0]iflen(nums)==2:returnmax(nums[0],nums[1])iflen(nums)==3:returnmax(nums)#不要窃取第一个dp=[nums[1],max(nums[1],nums[2])]n=len(nums)foriinrange(3,n):dp[0],dp[1]=dp[1],max(dp[0]+nums[i],dp[1])money_without_first=dp[1]#不偷最后dp=[nums[0],max(nums[0],nums[1])]foriinrange(2,n-1):dp[0],dp[1]=dp[1],max(dp[0]+nums[i],dp[1])money_without_last=dp[1]returnmax(money_without_first,money_without_last)516.最长回文子序列给定一个字符串s，找到最长的回文子序列并返回该序列的长度。可以假定s的最大长度为1000。示例1：输入：“bbbab”输出：4一个可能的最长回文子序列是“bbbb”。示例2：输入：“cbbd”输出：2一个可能的最长回文子序列是“bb”。deflongestPalindromeSubseq(s)->int:n=len(s)ifn<=1ors[::-1]==s:returnndp=[0]*nforiinrange(n-1,-1,-1):temp=0dp[i]=1forjinrange(i+1,n):如果s[i]==s[j]:temp,dp[j]=dp[j],temp+2else:temp=dp[j]如果dp[j-1]>dp[j]:dp[j]=dp[j-1]返回dp[-1]674。最长连续递增序列给定一个未排序的整数数组，找到最长连续递增序列并返回该序列的长度。示例1：输入：[1,3,5,4,7]输出：3解释：最长的连续递增序列是[1,3,5]，长度为3。虽然[1,3,5,7]也是一个上升的子序列，它不是连续的，因为在原始数组中5和7被4隔开。示例2：输入：[2,2,2,2,2]输出：1解释：最长的连续递增序列为[2]，长度为1。注意：数组的长度不会超过10000。这也是一个典型的动态规划问题状态：以i结尾的最长递增子序列的长度，$f(i)$choice：是否将当前数添加到之前的最长子序列中。状态转移方程：$$\begin{align}f(n)=\begin{cases}f(n-1)+1,if(nums[n-1]>nums[n-2])\\1,else\end{cases}\end{align}$$deffindLengthOfLCIS(nums)->int:ifnotnumsorlen(nums)==0:return0iflen(nums)==1:return1#状态转换方程为：dp(i)=dp(i-1)+1ifnums[i]>nums[i-1]else1res=1dp=1n=len(nums)foriinrange(1,n):如果nums[i]>nums[i-1]:dp=dp+1res=max(res,dp)否则：dp=1返回res
