最長回文串
給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
示例 1：
輸入: “babad”
輸出: “bab”
注意: “aba” 也是一個有效答案。
示例 2：
輸入: “cbbd”
輸出: “bb”
解題思路：回文串本身就具有狀态轉移的性質：删除回文串的頭尾兩個字元還是回文串，是以就可以使用動态規劃的方法解決。
我們使用dp[i][j]儲存狀态（以下用P(i,j)表示），表示字元串s的第i到j個字元組成的子串是否為回文串：
這裡的其他情況包含可能性：
1.子串s_i…s_j本身不是回文串；
2.i>j，此時子串不合法。
是以，動态規劃的狀态轉移方程為：
即隻有 s[i+1:j−1] 是回文串，并且 s 的第 i 和 j 個字母相同時，s[i:j] 才會是回文串。
上述的情況建立在子串長度大于2的前提，當子串長度為1，必然是個回文串；當子串長度為2，需要判斷兩個字元是否相同。是以我們就可以寫出動态規劃的邊界條件：
最終我們傳回所有狀态為True中的最大長度子串即為最長回文串。
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
#建立一個二維數組儲存狀态
dp = [[False] * n for _ in range(n)]
ans = ""
#枚舉子串長度為L+1
for L in range(n):
# 枚舉子串的起始位置 i，這樣可以通過 j=i+L 得到子串的結束位置
for i in range(n):
#j為子串的結束位置
j = i+L
#結束位置超過最大長度停止
if j >= len(s):
break
#長度為1的子串為回文串
if L == 0:
dp[i][j] = True
#長度為2的子串判斷兩個字元是否相同
elif L == 1:
dp[i][j] = (s[i] == s[j])
#狀态轉移方程
else:
dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
#傳回最大長度的回文串
if dp[i][j] and L + 1 > len(ans):
ans = s[i:j+1]
return ans
編輯距離
給你兩個單詞 word1 和 word2，請你計算出将 word1 轉換成 word2 所使用的最少操作數 。
你可以對一個單詞進行如下三種操作：
插入一個字元
删除一個字元
替換一個字元
示例 1：
輸入：word1 = “horse”, word2 = “ros”
輸出：3
解釋：
horse -> rorse (将 ‘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 (插入 ‘u’)
解題思路：我們從末尾看起，如果最後一個字元相同，那麼隻需對之前的字元進行操作，否則操作次數+1，對之前的字元操作時，選擇操作次數最小的一種，然後重複這個過程。
首先了解編輯的含義：
1.如果word1[i] == word2[j]，那麼比較word1[0…i-1]和word2[0…j-1] ；
2.否則，有三個選項：
a.執行插入操作，在word1末尾插入word2[j]後，末尾相同，隻需比較之前的字元，即word1[0…i]和word2[0…j-1]；
b.執行删除操作，删除word[i]後，比較word1[0…i-1]和word2[0…j]；
c.執行替換操作，替換後比較word1[0…i-1]和word2[0…j-1]
最後在上述三個結果中次數最少的+1
由于涉及了子問題，可以使用自頂向下的遞歸或者自底向上的動态規劃。
在遞歸的求解方式中，有太多的重複計算，可以建立一個二維數組儲存狀态進行優化。
動态規劃求解則需先寫出狀态轉移方程，因為是兩個字元串，有兩個對應的狀态，我們建立一個二維數組dp[i][j]儲存狀态，根據上述的解釋，我們可以得到：
1.若word1[i] == word2[j]，那麼dp = dp[i-1][j-1]
2.否則，dp[i][j] = 1 + min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]）
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n = len(word1)
m = len(word2)
#其中一個字元串為空串時，相當于在空串中插入另一個字元串
if n * m == 0:
return n + m
#建立二維數組儲存狀态
dp = [[0] * (m+1) for _ in range(n+1)]
#邊界狀态初始化,即目前長度的字元串插入到空串所需的次數
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = j
#根據狀态轉移方程計算所有dp值
for i in range(1, n+1):
for j in range(1, m+1):
#如果最後一個字元不同，需要多一步操作，否則直接計算之前的字元串
if word1[i-1] != word2[j-1]:
dp[i-1][j-1] += 1
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] - 1)
return dp[n][m]
時間複雜度：O(mn)，即為周遊兩個字元串數組長度。
空間複雜度：O(mn)，需要額外開創一個數組記錄狀态。
打家劫舍
你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組，計算你不觸動警報裝置的情況下 ，一夜之内能夠偷竊到的最高金額。
示例 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 。
解題思路：如果隻有一間屋子，那麼最高金額就是這間房的金額；如果隻有兩間房屋，由于相鄰的房屋無法同時偷竊，是以最高金額就是這兩間房的最大值；當房間數量大于2時，我們就要分情況考慮了。
當K>2時，對于第K間房，我們有偷竊或不偷竊兩個選擇：
1.偷竊第K間房，無法偷竊第K-1間房，最高金額為目前第K間房的金額以及前K-2間房的最高總金額；
2.不偷竊第K間房，最高金額為前K-1間房的最高總金額。
由于隻有一個狀态進行轉移，使用一位數組dp[i]表示前i間房能偷竊到的最高總金額，狀态轉移方程為：
有了方程我們還需要考慮邊界條件：
最後我們需要的答案就是dp[size-1]，其中size為數組長度。
class Solution:
def rob(self, nums: List[int]) -> int:
#一間房都沒有，偷了個寂寞
if not nums:
return 0
#房子數量
size = len(nums)
#隻有一間房，隻能偷他家了
if size == 1:
return nums[0]
#建立數組儲存狀态
dp = [0] * size
#設定邊界條件
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
#執行動态轉移
for i in range(2, size):
dp[i] = max(nums[i] + dp[i-2], dp[i-1])
return dp[size-1]
上述方法使用了額外數組存儲結果，其實每間房屋的最高總金額之和該房子前兩間房的最高總金額相關，是以可以使用滾動數組，每個時刻隻存儲前兩間房的最高總金額：
對于[2,7,9,3,1]
[2,7]，first=2，second=max(2,7)=7
[2,7,9]，first=second=7,second = max(2+9,second)=11
[2,6,9,3]，first=second=11，second=max(7+3,second)=11
[2,7,9,3,1]，first=second=11, second=max(11+1, second)=12
最終傳回second=12
class Solution:
def rob(self, nums: List[int]) -> int:
#一間房都沒有，偷了個寂寞
if not nums:
return 0
#房子數量
size = len(nums)
#隻有一間房，隻能偷他家了
if size == 1:
return nums[0]
first, second = nums[0], max(nums[0], nums[1])
for i in range(2, size):
first, second = second, max(first + nums[i], second)
return second
時間複雜度：O(n)，周遊一次數組
空間複雜度：O(1),使用滾動數組的方法則不再需要額外開創一個數組。
打家劫舍||
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房内都藏有一定的現金。這個地方所有的房屋都圍成一圈，這意味着第一個房屋和最後一個房屋是緊挨着的。同時，相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。
示例 1:
輸入: [2,3,2]
輸出: 3
解釋: 你不能先偷竊 1 号房屋（金額 = 2），然後偷竊 3 号房屋（金額 = 2）, 因為他們是相鄰的。
示例 2:
輸入: [1,2,3,1]
輸出: 4
解釋: 你可以先偷竊 1 号房屋（金額 = 1），然後偷竊 3 号房屋（金額 = 3）。
偷竊到的最高金額 = 1 + 3 = 4 。
解題思路：此題中的房間是環裝排列的，其實就是在上一題的基礎上掐頭或者去尾，是以我們可以吧資料分為兩組，其中一組不包含頭，求出最大金額p1，另一組不包含尾，求出最大金額p2，分别使用上一節的方法求解後，取兩者的最大值max(p1,p2)。
class Solution:
def rob(self, nums: List[int]) -> int:
#一間房都沒有，偷了個寂寞
if not nums:
return 0
#房子數量
size = len(nums)
#隻有一間房，隻能偷他家了
if size == 1:
return nums[0]
#否則将數組分為兩組
nums1 = nums[:size-1]
nums2 = nums[1:]
size1 = len(nums1)
size2 = len(nums2)
if size1 == 1 and size2 == 1:
return max(nums1[0], nums2[0])
first1, second1 = nums1[0], max(nums1[0], nums1[1])
for i in range(2, size1):
first1, second1 = second1, max(first1 + nums1[i], second1)
first2, second2 = nums2[0], max(nums2[0], nums2[1])
for i in range(2, size2):
first2, second2 = second2, max(first2 + nums2[i], second2)
return max(second1, second2)
代碼又臭又長，可以把中間将數組分為兩組的部分略去，直接寫在循環條件中：
class Solution:
def rob(self, nums: List[int]) -> int:
#一間房都沒有，偷了個寂寞
if not nums:
return 0
#房子數量
size = len(nums)
#隻有一間房，隻能偷他家了
if size == 1:
return nums[0]
#否則将數組分為兩組
first1, second1 = 0, 0
for num in nums[:-1]:
first1, second1 = second1, max(first1 + num, second1)
first2, second2 = 0, 0
for num in nums[1:]:
first2, second2 = second2, max(first2 + num, second2)
return max(second1, second2)
還是有代碼複用的情況，可以寫個函數：
class Solution:
def rob(self, nums: List[int]) -> int:
def maxrob(mynums):
first, second = 0, 0
for num in mynums:
first, second = second, max(first + num, second)
return second
return max(maxrob(nums[:-1]), maxrob(nums[1:])) if len(nums) != 1 else nums[0]
最長回文子序列
給定一個字元串 s ，找到其中最長的回文子序列，并傳回該序列的長度。可以假設 s 的最大長度為 1000 。
示例 1:
輸入:
“bbbab”
輸出:
4
一個可能的最長回文子序列為 “bbbb”。
示例 2:
輸入:
“cbbd”
輸出:
2
一個可能的最長回文子序列為 “bb”。
提示：
1 <= s.length <= 1000
s 隻包含小寫英文字母
解題思路：與子串不同，子序列不要求連續，隻要求順序一緻，如abcd中abd是子序列，雖然不連續但順序一緻，而acb則不是，因為與原本字元串的順序不同。
結合之前做過的最長回文子串，可以想到一個字元串如果頭尾相同，那麼就看去掉頭尾之後的中間部分是否為回文，否則，就看去掉頭的字元串以及去掉尾的字元串，分别檢視是否為回文。這就有了一個動态轉移的過程，題目隻要求我們輸出回文子序列的最大長度，我們可以構造動态轉移方程：
dp[i][j]=dp[i+1][j-1] + 2 if（str[i]==str[j]）
dp[i][j]=max(dp[i+1][j],dp[i][j-1]) if （str[i]!=str[j]）
這裡的邊界條件為dp[i][i] = 1,每個字元串本身都是一個回文子序列。
需要注意的是i需要從大到小逆序周遊，因為計算dp[i][j]時需要計算dp[i+1][*]，而j則從小到大周遊，計算的是第i個字元到第j個字元，隻要保證j比i大即可：
最後傳回的結果即為dp[0][n-1]，n為數組長度
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
#計算dp[i][j]時需要計算dp[i+1][*]或dp[*][j-1]，是以i應該從大到小，即遞減；j應該從小到大，即遞增
for i in range(n-1, -1, -1):
dp[i][i] = 1
#計算的是字元i到字元j，需要保證j比i大
for j in range(i+1, n):
#如果頭尾兩個字元相同，則計算中間的字元
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
#否則分别計算去掉頭和尾的兩組字元串，再取其中最大值
else:
dp[i][j] = max(dp[i][j-1], dp[i+1][j])
return dp[0][n-1]
其中也看出動态規劃四個要素：
1.狀态dp，在該題中為最長回文子序列的長度；
2.轉移方程，即歸納，從已知結果中推出未知部分，比如已經知道子問題的dp[i+1][j-1]（該題中為s[i+1:j-1]中最長回文子序列的長度）的結果，如何推出dp[i][j]，如該題中我們發現這取決于前後兩個字元s[i]和s[j]是否相等；
3.邊界條件，最基本的情況是什麼；
4.傳回結果，根據dp數組的定義和題目要求傳回。
再者，還有思路模闆，分别是一維和二維的dp數組，視需要儲存的狀态數而定：
模闆1：
int n = array.length;
int[] dp = new int[n];
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
dp[i] = 最值(dp[i], dp[j] + ...)
}
}
模闆2：
int n = arr.length;
int[][] dp = new dp[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j])
dp[i][j] = dp[i][j] + ...
else
dp[i][j] = 最值(...)
}
}
這種思路運用相對更多一些，尤其是涉及兩個字元串/數組的子序列。
最長連續遞增序列
給定一個未經排序的整數數組，找到最長且連續的的遞增序列，并傳回該序列的長度。
示例 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。
解題思路：直接周遊，逐一比較，然後統計最長的連續遞增序列就好了。做法很簡單，主要還是思考如何優化。
滑動視窗法：
每個連續遞增的子序列是不相交的，一個數在第一個遞增子序列出現後，不可能在另一個遞增子序列出現，是以就有一個邊界，也就是nums[i-1]≥nums[i]的時候，遞增子序列就停止了，開始計算下一個遞增子序列，我們把此時的i儲存在一個變量count中。候選答案為i-count+1，每次周遊更新候選答案的最大值。
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
ans = count = 0
for i in range(len(nums)):
if i and nums[i-1] >= nums[i]:
count = i
ans = max(ans, i - count + 1)
return ans
動态規劃：
定義dp[i]為連續遞增序列長度。
邊界情況為:
1.當nums[i-1]≥nums[i]時，dp[i]=1
2.dp[0] = 1
狀态轉移方程：dp[i] = dp[i-1] + 1
傳回：max(dp)
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
dp = [0] * n
dp [0] = 1
for i in range(n):
dp[i] = dp[i-1] + 1 if nums[i] > nums[i-1] else 1
return max(dp)
總結
動态規劃難在思維，需要通過歸納總結出一個合适的狀态轉移方程。一般解題按如下步驟：
第一步：确定動态規劃狀态
第二步：寫出狀态轉移方程
第三步：考慮初始化條件
第四步：考慮輸出狀态
第五步：考慮對時間，空間複雜度的優化