LeetCode 97. Interleaving String

O(MN) Space dp[i][j]表示isInterleave(self, s1[:i], s2[:j], s3[:i+j]). 初始状态: dp[i][0]=True if dp[i-1][0]==True and s1[i-1]==s3[i-1] dp[0][i]=True if dp[0][i-1]==True and s2[i-1]==s3[i-1] 递推公式: dp[i][j]=(s1[i-1]==s3[i+j-1] and dp[i-1][j]) or (s2[j-1]==s3[i+j-1] and dp[i][j-1]) 分别是从s1取下一个

LeetCode 53. Maximum Subarray

这一题有O(N)的DP解法和O(NlogN)的DC解法 动态规划 dp[i]表示以i结尾的asubarray的最大和。 初始状态: dp[0]=nums[0] 递推公式: If dp[i-1]<0,

LeetCode 32. Longest Valid Parentheses

三个解法 动态规划解法 代码如下: class Solution: def longestValidParentheses(self, s): length = [0]*len(s) for i in range(len(s)): if s[i]=='(': length[i] = 0 elif i-1>=0: if s[i-1]=='(': length[i] = (length[i-2] if i-2>=0 else 0)+2 elif i-1-length[i-1]>=0 and s[i-1-length[i-1]]=='(': length[i] = 2+length[i-1]+(length[i-2-length[i-1]] if i-2-length[i-1]>=0 else 0) return max(length) if len(s)>0 else 0 栈解法 栈解法,遇到匹

Leetcode Weekly Contest 78

808. Soup Servings 这一题最重要的一点就是Notes里的一行提示:Answers within 10^-6 of the true value will be accepted as correct.。所以说审题很重要啊= =。 因为这行提示

LeetCode 198. House Robber

这一题还是一道简单的动态规划题。搞一个dp数组,dp[i]表示抢劫前i个房子的最大收获。所以dp[i+1]有两种选择: 不抢劫第i个房子,所以

LeetCode 72. Edit Distance

edit distance经常用来计算文档的相似度,这一题是一道经典的动态规划题。搞一个dp数组dp[i][j]表示w1[:i]和w2[:j]的ed

LeetCode 435. Non-overlapping Intervals

这一题是很常见的一道区间的问题,其他的外壳如task schedule。 只需要把区间按结束点排序,然后尽量从左往右遍历一次即可。代码如下: class Solution: