列表-子序列(連續/不連續)
字符串-子序列(不連續)，子串(連續)

---

1.一維dp，dp[i] --以item[i]結尾的，有效的，最長XXX的長度

---

1.LeetCode-32 最長有效括號–子串

題目：給定一個只包含 ‘(’ 和 ‘)’ 的字符串s，找出最長的包含有效括號的子串的長度。

dp[i] --以s[i]結尾的，有效的子串的長度中，最長的一個。

顯然有效的子串一定以)結尾，因此我們可以知道以(結尾的子串對應的dp 值必定為 0，我們只需要求解 )在dp 數組中對應位置的值。

同時因為子串要求連續，所以可以用相鄰的dp[i-2]來更新符合條件的dp[i]($s[i]==")"ands[i?1]=="("=>dp[i]=dp[i?2]+2$})

# 1.s[i]==")" and s[i-1]=="("    dp[i] = dp[i-2]+2
# 2.s[i]==")" and s[i-1]==")"    dp[i] = dp[i-1] + dp[i-dp[i-1]-2]+2 下標的合理性
# ((xx)) dp[i-1] 也有效的情況下
def longestValidParentheses(self, s):n=len(s)if n<2:return 0dp=[0]*nres=0for i in range(1,n):if i==1:if s[i]==")" and s[i-1]=="(":dp[1]=2else:if s[i]==")" and s[i-1]=="(":dp[i]=dp[i-2]+2               if s[i]==")" and s[i-1]==")":if i-1-dp[i-1]>=0 and s[i-1-dp[i-1]]=="(":dp[i]=dp[i-1]+2 # if i-2-dp[i-1]>=0:dp[i]+=dp[i-2-dp[i-1]]res=max(res,dp[i]) return res

2.LeetCode-300 最長上升子序列–長度

題目：給定一個無序的整數數組，找到其中最長上升子序列的長度。

輸入: [10,9,2,5,3,7,101,18]
輸出: 4 
解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。

dp[i] --以nums[i]結尾的，上升序列的長度中，最長的一個。

def lengthOfLIS(self, nums):""":type nums: List[int]:rtype: int"""# dp[i]表示以nums[i]為結尾的最長上升子序列的長度n = len(nums)if n < 2:return ndp = [1] * nres = 0for i in range(1,n):for j in range(i):if nums[j]< nums[i]:dp[i] = max(dp[i], dp[j]+1)res = max(res, dp[i])               # 這么寫就需要考慮初值為1的時候return res

---

2.維度d

---

3.LeetCode-32 最長回文子串–是什么

獨自一個人也，也可以二維dp, 強！二維dp實際上也是以每個字符為中心向兩邊擴展的情況。
dp[i][j] 表示s[i]-s[j]子串是否是回文子串，依賴于s[i]==s[j] and dp[i+1][j-1]
狀態轉移決定了dp初始化元素(對角線)和更新的方向(由下向上，由對角線往右)

def longestPalindrome(self, s):n = len(s)if n < 2:          # 空字符和單個字符直接輸出return sdp = [[False] * n for _ in range(n)]for i in range(n):dp[i][i] = Trueres_str, res_len = s[0], 1    # 兩個字符的的時候，不相等時結果為單個字符for i in range(n-2,-1,-1):for j in range(i+1, n):if j == i+1:          # 次對角線上的元素單獨判斷。if s[i] == s[j]:dp[i][j] = Trueif j-i+1 > res_len:res_str = s[i:j+1]res_len = j - i + 1else:if s[i] == s[j] and dp[i+1][j-1]:dp[i][j] = Trueif j-i+1 > res_len:res_str = s[i:j+1]res_len = j - i + 1return res_str  

5.LeetCode-512 最長回文子序列–長度

和上題的基本思路一樣，不過dp數組表示的含義變為
dp[i][j] 表示s[i]-s[j]子串中回文序列的長度

# if s[i]==s[j]：dp[i][j] = dp[i+1][j-i]+2，
# if s[i]!=s[j]：dp[i][j] = max(dp[i+1][j],dp[i][j-1])
def longestPalindromeSubseq(self, s):n = len(s)if n < 2:return ndp = [[0] * n for _ in range(n)]for i in range(n):dp[i][i] = 1for i in range(n-2, -1, -1):for j in range(i+1,n):if s[j] == s[i]:dp[i][j] = dp[i+1][j-1] + 2else:dp[i][j] = max(dp[i+1][j], dp[i][j-1])return dp[0][n-1]

6.LeetCode-1143 最長公共子序列–長度

(兩個字符串，二維dp 才是標配嘛)
dp[i][j] 表示s1[0]-s1[i] 于s2[0]-s2[j] 的最長公共子序序列，更新形式于512題類似，只不過初值和方向不大一樣，初值為第0行第0列均為0，方向由上到下，由左到右。

def longestCommonSubsequence(self, text1, text2):l1, l2 = len(text1), len(text2)dp = [[0] * (l2 + 1) for _ in range(l1 + 1)]for i in range(1, l1 + 1):for j in range(1, l2 + 1):if text1[i-1] == text2[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])# return dp[-1][-1]#  回溯 只有加res_str=[""]*dp[-1][-1]i,j=l1,l2while(i>0):if dp[i][j]>dp[i-1][j]:                   # 比上面的大，不是來上面if dp[i][j]>dp[i][j-1]:				  # 	比左邊的大，不是來自左邊res_str[dp[i][j]-1]=text1[i-1]    # 		來自對角線操作else:                                 # 	沒有左邊大，來自左邊 橫坐標操作i+=1							  # 		i 需要先+1，最后的-1會抵消j-=1								  # 	沒有左邊大，來自左邊，縱坐標操作i-=1print(res_str)

---

3.帶技巧解題

---

6.LeetCode-128 最長連續序列–長度

給定一個未排序的整數數組，找出最長連續序列的長度。要求算法的時間復雜度為 O(n)。

數組本身無序，連續序列有序，只要能找到連續序列的開頭，就能確定序列長度，迭代更新最長長度就可以了。

def longestConsecutive(self, nums):if not nums:return 0res = 1nums_set = set(nums)for val in nums_set:if val - 1 not in nums_set:     # val 為連續序列的開頭count = 1num = valwhile(num + 1 in nums_set):count += 1num = num + 1res = max(res, count)return res

7.LeetCode-14 最長公共前綴-字符串

暴力法：縱向掃描
先驗：最長公共前綴不回比最短的字符串長，所以先求出最短的長度。

def longestCommonPrefix(self, strs):""":type strs: List[str]:rtype: str"""n = len(strs)if n == 0:return ""min_l = float("INF")for string in strs:min_l = min(len(string), min_l)i = 0con_pre = ""while(i < min_l):con_pre = strs[0][:i+1]for string in strs:if string[:i+1] != con_pre:return con_pre[:i]i += 1return con_pre

8.劍指offer-48 最長不含重復字符串的子字符串-長度

請從字符串中找出一個最長的不包含重復字符的子字符串，計算該最長子字符串的長度。

輸入: "abcabcbb"
輸出: 3 
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。

移動窗口，保證窗口內的字符無重復，如果有重復就縮小窗口。

def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""win = {}left, right = 0, 0n = len(s)res = 0while (right < n):c1 = s[right]if win.get(c1):win[c1] += 1else:win[c1]  = 1right += 1while(win[c1]>1):c2 = s[left]win[c2] -=1left += 1res  = max(res, right - left)return res