LeetCode-4-動態規劃

—-
title: LeetCode-4-動態規劃
date: 2020-01-19 11:28:41
tags: LeetCode
categories:

- 數據結構與算法
- LeetCode

四、動態規劃

動態規劃三大步驟：

動態規劃，無非就是利用歷史記錄，來避免我們的重複計算。而這些歷史記錄，我們得需要一些變量來保存，一般是用一維數組或者二維數組來保存。

第一步驟：定義數組元素的含義，上面說了，我們會用一個數組，來保存歷史數組，假設用一維數組 dp[] 吧。這個時候有一個非常非常重要的點，就是規定你這個數組元素的含義，例如你的 dp[i] 是代表什麼意思？

第二步驟：找出數組元素之間的關係式，我覺得動態規劃，還是有一點類似於我們高中學習時的歸納法的，當我們要計算 dp[n] 時，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，來推出 dp[n] 的，也就是可以利用歷史數據來推出新的元素值，所以我們要找出數組元素之間的關係式，例如 dp[n] = dp[n-1] + dp[n-2]，這個就是他們的關係式了。而這一步，也是最難的一步，後面我會講幾種類型的題來說。

第三步驟：找出初始值。學過數學歸納法的都知道，雖然我們知道了數組元素之間的關係式，例如 dp[n] = dp[n-1] + dp[n-2]，我們可以通過 dp[n-1] 和 dp[n-2] 來計算 dp[n]，但是，我們得知道初始值啊，例如一直推下去的話，會由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我們必須要能夠直接獲得 dp[2] 和 dp[1]的值，而這，就是所謂的初始值。

由了初始值，並且有了數組元素之間的關係式，那麼我們就可以得到 dp[n] 的值了，而 dp[n] 的含義是由你來定義的，你想求什麼，就定義它是什麼，這樣，這道題也就解出來了。

原文：https://mp.weixin.qq.com/s/pg-IJ8rA1duIzt5hW1Cycw

?5.最長回文子串

連結：https://leetcode-cn.com/problems/longest-palindromic-substring/

給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
示例 2：

輸入: "cbbd"
輸出: "bb"

題解一|暴力破解：
   很明顯，暴力法將選出所有子字符串可能的開始和結束位置，並檢驗它是不是回文。
   時間複雜度：O(n^2),往往利用python的切片可以很好的縮減複雜度
   如果不用切片，還需要遍歷一次子字符串，時間複雜度就是O(n^3)
   空間複雜度：O(1)

class Solution:
def longestPalindrome(self, s: str) -> str:
if s==s[::-1]:
return s

maxLen=1
ans=s[0]
for i in range(0,len(s)-1):
for j in range(i+1,len(s)):
if j-i+1 > maxLen and self.isPalindrome(s[i:j+1]):
maxLen=j-i+1
ans=s[i:j+1]
return ans

def isPalindrome(self, s: str) -> bool:
left,right=0,len(s)-1
while left<right:
while left<len(s) and not s[left].isalnum():
left+=1
while right >-1 and not s[right].isalnum():
right-=1
if left>right:
return True
if s[left].upper() != s[right].upper():
return False
else:
left+=1
right-=1
return True

時間複雜度：O(N^3)，這裡 N 是字符串的長度，枚舉字符串的左邊界、右邊界，然後繼續驗證子串是否是回文子串，這三種操作都與 N 相關；
空間複雜度：O(1)，只使用到常數個臨時變量，與字符串長度無關。

class Solution:
# 暴力匹配（超時）
def longestPalindrome(self, s: str) -> str:
# 特判
size = len(s)
if size < 2:
return s

max_len = 1
res = s[0]

# 枚舉所有長度大於等於 2 的子串
for i in range(size - 1):
for j in range(i + 1, size):
if j - i + 1 > max_len and self.__valid(s, i, j):
max_len = j - i + 1
res = s[i:j + 1]
return res

def __valid(self, s, left, right):
# 驗證子串 s[left, right] 是否為回文串
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True

class Solution:
def longestPalindrome(self, s: str) -> str:
if s==s[::-1]:
return s

maxLen=1
ans=s[0]
for i in range(0,len(s)-1):
for j in range(i+1,len(s)):
if j-i+1 > maxLen and s[i:j+1]==s[i:j+1][::-1]: # arr='abb',arr[0:1]='a',右邊是開區間
maxLen=j-i+1
ans=s[i:j+1]
return ans

題解二|每個字母當成回文串的中心：

考慮兩種情況:回文串的長度為奇數或者偶數情況。

class Solution:
def longestPalindrome(self, s: str) -> str:
n=len(s)
self.res=''
def helper(i,j):
while i>= 0 and j<n and s[i]==s[j]:
i-=1
j+=1
if len(self.res) < j-i-1:
self.res=s[i+1:j]
# print(i,self.res)

for i in range(n):
helper(i,i)
helper(i,i+1) # 解決case為"cbbd",即解決回文串為偶數的情況
return self.res

題解三|把每個字母當成回文串的結束：

class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ""
max_len = 1
n = len(s)
start = 0
for i in range(1,n):
even = s[i-max_len:i+1]
odd = s[i - max_len-1:i+1]
#print(even,odd)
if i - max_len - 1 >= 0 and odd == odd[::-1]:
start = i - max_len - 1
max_len += 2
elif i - max_len >=0 and even == even[::-1]:
start = i - max_len
max_len += 1

#print(start,max_len)
return s[start: start+max_len]

題解四|動態規劃：

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/

1、定義數組的定義
dp[i][j] 表示子串 s[i,j] 是否為回文子串。
2、找出數組的關係式
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
3、找到初始值

試想如果 dp[l][r]=true，我們要判斷 dp[l-1][r+1] 是否為回文。
只需要判斷字符串在(l-1)和（r+1)兩個位置是否為相同的字符，是不是減少了很多重複計算。

初始狀態，l=r 時，此時 dp[l][r]=true
狀態轉移方程，dp[l][r]=true 並且(l-1)和（r+1)兩個位置為相同的字符，此時 dp[l-1][r+1]=true。

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/gao-hao-dong-tai-gui-hua-he-zhong-xin-tuo-zhan-zhu/

class Solution:
def longestPalindrome(self, s: str) -> str:
if not s or len(s) <2:
return s

length=len(s)
start=0
end=0
count=1

dp=[[0]* length for i in range(length)]
for r in range(1,length):
for l in range(0,length):
if (s[l]==s[r]) and (r-l<=2 or dp[l+1][r-1]):
dp[l][r]=True
if r-l+1> count:
count=r-l+1
start=l
end=r
return s[start:end+1]

class Solution:
def longestPalindrome(self, s: str) -> str:
# 觀察是否存在狀態，例如 babab,可知aba是迴文序列，那麼可以看出babab也是迴文序列，當b = b的時候
# 因此我們可以用二維數組來i,j表示回文串的起始和結尾索引位置。
# 狀態轉移方程dp[i,j] = dp[i+1][j-1] if s[i] == s[j] else False
# 接下來看有沒有特殊的邊界情況存在，我們發現當0<=j-i<3的時候，只要滿足s[i] == s[j]，無論裡面是什麼dp[i,j]都會是回文字串,將這種情況分開討論，當j-i>=3的時候，進行狀態轉移
# 初始值
m = len(s)
max_len = 1
start_index = 0
if m < 2:
return s
dp = [[False for _ in range(m)] for _ in range(m)]
for j in range(1,m):
for i in range(0,j):
if s[i] == s[j]:
if j-i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i+1][j-1]
else:
dp[i][j] = False
if dp[i][j]:
cur_len = j-i+1
if cur_len > max_len:
max_len = cur_len
start_index = i
return s[start_index:start_index+max_len]

class Solution:
def longestPalindrome(self, s: str) -> str:
if(not s or len(s)==1):
return s
n=len(s)
dp=[[False]*n for _ in range(n)]
max_len=1
start=0
for i in range(n):
dp[i][i]=True
if(i<n-1 and s[i]==s[i+1]):
dp[i][i+1]=True
start=i
max_len=2
for l in range(3,n+1):
for i in range(n+1-l):
r=i+l-1
if(s[i]==s[r] and dp[i+1][r-1]):
dp[i][r]=True
start=i
max_len=l
return s[start:start+max_len]

53.最大子序和

連結：https://leetcode-cn.com/problems/maximum-subarray/

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。
進階:

如果你已經實現複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

暴力——動態規劃——貪心——分治?
https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-cshi-xian-si-chong-jie-fa-bao-li-f/
題解一：

遍歷整個數組，在數組的每一個位置時，求出一個全局最大值L，代表以當前位置
為結尾的最大字串，而G是當前位置的L和上一個位置L相比較後，取數值更大的。
當遍歷到i時，以i個為結尾的最大字串就是我們的L。
數組[-2,1,-3,4,-1,2,1,-5,4]
位置0：L=-2,G=-2
位置1：L=1,G=1
位置2：L=-2，G=1
位置3：L=4，G=4
位置4：L=3，G=4
位置5：L=5，G=5
位置6：L=6，G=6
位置7：L=-1，G=6
位置8：L=4，G=6
最後，全局最大值G就是我們的結果。

class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l=g=-10000000000
for n in nums:
l=max(n,l+n)
g=max(l,g)
return g

題解二：

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
nums[i]=max(nums[i],nums[i]+nums[i-1])

return max(nums) # 取子序和中最大值

題解三|動態規劃:
   1、定義數組元素的含義

dp[i]為以num[i]結尾的子段的最大子段和
dp[1]為以num[1]結尾的最大子段和

2、尋找遞推表達式

只考慮第一個元素，則最大子段和為其本身 dp[0] = nums[0]

考慮前兩個元素，最大子段和為 nums[0],num[1]以及 nums[0] + num[1] 中最大值 設為dp[1]

考慮前三個元素，如何求其最大子段和？還是分為兩種情況討論，第三個元素在最後的字串內嗎？

若第三個元素也包含在最後的字串內，則dp[2] = Max(dp[1]+nums[2] , nums[2])

dp[i]=max(dp[i-1]+num[i],num[i])

3、找出初始值

dp[0]=num[0]
dp[1]=max(dp[0]+num[1],num[1])

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
lens=len(nums)
if lens==0:
return 0
dp=lens*[0]
dp[0]=nums[0]
# dp[1]=max(dp[0]+nums[1],nums[1])
res=dp[0]
for i in range(1,lens):
dp[i]=max(dp[i-1]+nums[i],nums[i])
if dp[i]>res:
res=dp[i]
return res

輸入：
[-2,1,-3,4,-1,2,1,-5,4]
輸出：
[-2, 1, 0, 0, 0, 0, 0, 0, 0]
[-2, 1, -2, 0, 0, 0, 0, 0, 0]
[-2, 1, -2, 4, 0, 0, 0, 0, 0]
[-2, 1, -2, 4, 3, 0, 0, 0, 0]
[-2, 1, -2, 4, 3, 5, 0, 0, 0]
[-2, 1, -2, 4, 3, 5, 6, 0, 0]
[-2, 1, -2, 4, 3, 5, 6, 1, 0]
[-2, 1, -2, 4, 3, 5, 6, 1, 5]

62.不同路徑

連結：https://leetcode-cn.com/problems/unique-paths/

一個機器人位於一個 m x n 網格的左上角 （起始點在下圖中標記為「Start」 ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為「Finish」）。

問總共有多少條不同的路徑？

例如，上圖是一個7 x 3 的網格。有多少可能的路徑？

說明：m 和 n 的值均不超過 100。

示例 1:

輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始，總共有 3 條路徑可以到達右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:

輸入: m = 7, n = 3
輸出: 28

題解一|動態規劃：

1、定義數組元素的含義
   目的：從左上角到右下角一共有多少種路徑
   dp[i][j]含義：從左上角走到(i,j)這個位置時，一共有dp[i][j]種路徑

2、找到數組的遞推關係式

如何才能到達 (i, j) 這個位置呢？可以向下走或者向右走，所以有兩種方式到達：

一種是從 (i-1, j) 這個位置走一步到達
一種是從(i, j - 1) 這個位置走一步到達

所以：dp[i][j]=dp[i-1][j]+dp[i][j-1]

3、找到初始值

當 dp[i][j] 中，如果 i 或者 j 有一個為 0，那麼還能使用關係式嗎？答是不能的，因為這個時候把 i - 1 或者 j - 1，就變成負數了，數組就會出問題了。

圖中的最上面一行和左邊一列，因此初始值如下：

dp[0][0….n-1] = 1; // 相當於最上面一行，只能一直往右走
dp[0…m-1][0] = 1; // 相當於最左面一列，只能一直往下走

時間複雜度：O(mn)
空間複雜度：O(mn)，使用dp數組保存結果

class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m<=0 or n<=0:
return 0
dp=[ n*[_] for _ in range(m)] # 定義二維數組
# print(dp)
for i in range(m):
dp[i][0]=1
for j in range(n):
dp[0][j]=1

for i in range(1,m):
for j in range(1,n):
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[m-1][n-1]

class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m<=0 or n<=0:
return 0
dp=[ m*[_] for _ in range(n)]
# print(dp)
for i in range(n):
dp[i][0]=1
for j in range(m):
dp[0][j]=1

for i in range(1,n):
for j in range(1,m):
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[n-1][m-1]

題解二|動態規劃優化:

參考：https://mp.weixin.qq.com/s?__biz=Mzg2NzA4MTkxNQ==&mid=2247486303&idx=1&sn=6034d1e6ca24253da64d6c539998f7c6&scene=21#wechat_redirect

轉化成一維，關係式為 dp[i] = dp[i] + dp[i-1]

空間複雜度：O(n)

class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m<=0 or n<=0:
return 0
dp=n*[0] # n是列
for i in range(n):
dp[i]=1

for i in range(1,m):
dp[0]=1
for j in range(1,n):
dp[j]=dp[j-1]+dp[j]
return dp[n-1]

63.不同路徑 II

連結：https://leetcode-cn.com/problems/unique-paths-ii/

一個機器人位於一個 m x n 網格的左上角 （起始點在下圖中標記為「Start」 ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為「Finish」）。

現在考慮網格中有障礙物。那麼從左上角到右下角將會有多少條不同的路徑？

如上圖

網格中的障礙物和空位置分別用 1 和 0 來表示。

說明：m 和 n 的值均不超過 100。

示例 1:

輸入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
輸出: 2
解釋:
3x3 網格的正中間有一個障礙物。
從左上角到右下角一共有 2 條不同的路徑：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

題解一|動態規劃：

1、定義數組元素的含義
   機器人從左上角走到(i, j) 這個位置時，一共有 dp[i][j] 種路徑
2、找出關係數組元素間的關係式
   想像以下，機器人要怎麼樣才能到達 (i, j)這個位置？由於機器人可以向下走或者向右走，所以有兩種方式到達。當遇到障礙時

一種是從 (i-1, j) 這個位置走一步到達

一種是從(i, j-1) 這個位置走一步到達

因為是計算所有可能的步驟，所以是把所有可能走的路徑都加起來，所以關係式是 dp[i][j] = dp[i-1][j] + dp[i][j-1]。（當沒有遇到障礙時，就用以上的方式進行）

3、找出初始值
   dp[0][0]=1

dp[0][i]=dp[0][i-1]; // 相當於最上面一行，機器人只能一直往右走（當沒有遇到障礙時）
dp[i][0]=dp[i-1][0]; // 相當於最左面一列，機器人只能一直往下走（當沒有遇到障礙時）

class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
if obstacleGrid is None:
return 0
if obstacleGrid[0][0]==1 or obstacleGrid[-1][-1] == 1:
return 0

m=len(obstacleGrid)
n=len(obstacleGrid[0])

dp=[n*[0] for _ in range(m)] # dp=[n*[_] for _ in range(m)]時結果有誤

dp[0][0]=1
for i in range(1,m):
if obstacleGrid[i][0] !=1:
dp[i][0]=dp[i-1][0]

for i in range(1,n):
if obstacleGrid[0][i] !=1:
dp[0][i]=dp[0][i-1]

for i in range(1,m):
for j in range(1,n):
if obstacleGrid[i][j] != 1:
dp[i][j]=dp[i-1][j]+dp[i][j-1]
# print(dp[m-1][n-1])
return dp[-1][-1]

64.最小路徑和

連結：https://leetcode-cn.com/problems/minimum-path-sum/

給定一個包含非負整數的 m x n 網格，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。

說明：每次只能向下或者向右移動一步。

示例:

輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因為路徑 1→3→1→1→1 的總和最小。

題解一|動態規劃：
1、定義數組元素的含義
   目的是從左上角到右下角，最小路徑和是多少。
   dp[i][j]含義：當從左上角走到(i,j)位置時，最小路徑和為dp[i][j]

定義二維數據，數組是從下標 0 開始算起的，所以右下角的位置是 (m-1, n - 1)，所以 dp[m-1][n-1] 就是我們所求。

2、找到數組的遞推關係式

如何才能到達 (i, j) 這個位置？由於可以向下走或者向右走，所以有兩種方式到達：

一種是從 (i-1, j) 這個位置走一步到達
一種是從 (i, j-1) 這個位置走一步到達

不過本次計算不是所有可能路徑，而是計算哪一個路徑和最小。

所以：dp[i][j]=min(dp[i-1][j],dp[i][j-1])+arr[i][j]

3、找到初始值

當 dp[i][j] 中，如果 i 或者 j 有一個為 0，那麼還能使用關係式嗎？答是不能的，因為這個時候把 i - 1 或者 j - 1，就變成負數了，數組就會出問題了，所以我們的初始值是計算出所有的 dp[0][0….n-1] 和所有的 dp[0….m-1][0]

dp[0][j] = arr[0][j] + dp[0][j-1]; // 相當於最上面一行，只能一直往左走
dp[i][0] = arr[i][0] + dp[i][0]; // 相當於最左面一列，只能一直往下走

時間複雜度：O(mn)
空間複雜度：O(mn)

class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# print(grid)
m=len(grid) # 行
n=len(grid[0]) # 列
if m<=0 or n<=0:
return 0
dp=[ n*[_] for _ in range(m)]
# print(dp)
dp[0][0]=grid[0][0]

for i in range(1,m):
dp[i][0]=dp[i-1][0]+grid[i][0]

for i in range(1,n):
dp[0][i]=dp[0][i-1]+grid[0][i]

for i in range(1,m):
for j in range(1,n):
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
# print(dp)

return dp[m-1][n-1]

70.爬樓梯

連結：https://leetcode-cn.com/problems/climbing-stairs/

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

示例 1：

輸入：2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階
示例 2：

輸入：3
輸出：3
解釋：有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

題解一|遞歸：

class Solution:
def climbStairs(self, n: int) -> int:
if n<=2:
return n
return self.climbStairs(n-1)+self.climbStairs(n-2)

題解二|動態規劃：
1、定義數組元素的含義

dp[i]含義：跳上第i個臺階總共有dp[i]種跳法；
dp[n]即為我們所求結果。

2、找出數組元素間的關係式

把一個規模比較大的問題分成幾個規模比較小的問題，然後由小的問題推導出大的問題。
到達第 n 級的臺階有兩種方式：
一種是從第 n-1 級跳上來
一種是從第 n-2 級跳上來
所以：dp[n] = dp[n-1] + dp[n-2]。

3、找出初始值

n=1時，dp[1]=dp[0]+dp[-1]，不允許下標為-1，所以dp[1]=1
n=0時，dp[0]=0
n=2時，dp[2]=dp[1]+dp[0]=1，所以以上初始值定義不嚴謹，因為dp[2]=2

時間複雜度：O(n)
空間複雜度：O(n)

class Solution:
def climbStairs(self, n: int) -> int:
if n<=2:
return n
dp=(n+1)*[0] # 注意是n+1
dp[1]=1
dp[2]=2
for i in range(3,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n] # 返回最後一個數

72.編輯距離

連結：https://leetcode-cn.com/problems/edit-distance/

給定兩個單詞 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')

思路：

if s1[i] == s2[j]:
啥都別做（skip）
i, j 同時向前移動
else:
三選一：
插入（insert）
刪除（delete）
替換（replace）

題解一|遞歸|自頂向下：

class Solution:
def minDistance(self, word1: str, word2: str) -> int:
def dp(i,j):
if i==-1:
return j+1
if j==-1:
return i+1
if word1[i]==word2[j]:
return dp(i-1,j-1) # 什麼都不做
else:
return min(
dp(i,j-1)+1, # 插入
dp(i-1,j)+1, # 刪除
dp(i-1,j-1)+1 # 替換
)
return dp(len(word1)-1,len(word2)-1)

解釋：

if s1[i] == s2[j]:
return dp(i - 1, j - 1) # 啥都不做
# 解釋：
# 本來就相等，不需要任何操作
# s1[0..i] 和 s2[0..j] 的最小編輯距離等於
# s1[0..i-1] 和 s2[0..j-1] 的最小編輯距離
# 也就是說 dp(i, j) 等於 dp(i-1, j-1)

dp(i, j - 1) + 1, # 插入
# 解釋：
# 我直接在 s1[i] 插入一個和 s2[j] 一樣的字符
# 那麼 s2[j] 就被匹配了，前移 j，繼續跟 i 對比
# 別忘了操作數加一

dp(i - 1, j) + 1, # 刪除
# 解釋：
# 我直接把 s[i] 這個字符刪掉
# 前移 i，繼續跟 j 對比
# 操作數加一

dp(i - 1, j - 1) + 1 # 替換
# 解釋：
# 我直接把 s1[i] 替換成 s2[j]，這樣它倆就匹配了
# 同時前移 i，j 繼續對比
# 操作數加一

優化：

class Solution:
def minDistance(self, word1: str, word2: str) -> int:
memo=dict()

def dp(i,j):
if (i,j) in memo:
return memo[(i,j)]
if i==-1:
return j+1
if j==-1:
return i+1
if word1[i]==word2[j]:
memo[(i,j)] = dp(i-1,j-1) # 什麼都不做
else:
memo[(i,j)]= min(
dp(i,j-1)+1, # 插入
dp(i-1,j)+1, # 刪除
dp(i-1,j-1)+1 # 替換
)
return memo[(i,j)]
return dp(len(word1)-1,len(word2)-1)

題解二|動態規劃：

思路：

理解 word1 上的刪除等價 word2 上的增加, word1 上的增加等價於 word2 上的刪除
2維的 dp array 中某一點 dp[i][j] 的意義: word1[ : i] 到 word[ : j] 轉換所需要的最小的數目
不太需要關注具體進行了刪除、增加還是替換操作，而是專注於 a 狀態到 b 狀態所需要的步數

class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
dp = [[float('inf') for _ in range(n + 1)] for _ in range(m + 1)]
# 初始化
for i in range(m + 1):
dp[i][0] = i
for i in range(n + 1):
dp[0][i] = i
# 狀態轉移
# i , j 代表 word1, word2 對應位置的 index
for i in range(1, m + 1):
for j in range(1, n + 1):
# 如果word1[:i][-1]==word2[:j][-1]
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
# 否則從三種狀態中選一個最小的然後 +1
else:
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1
return dp[m][n]

題解三|動態規劃：

參考：https://mp.weixin.qq.com/s?__biz=Mzg2NzA4MTkxNQ==&mid=2247486294&idx=1&sn=dd8968700d19ea8b1db29065dc2f7b01&scene=21#wechat_redirect

1、定義數組元素的含義

目的：求將 word1 轉換成 word2 所使用的最少操作數 。

dp[i][j]的含義為：當字符串 word1 的長度為 i，字符串 word2 的長度為 j 時，將 word1 轉化為 word2 所使用的最少操作次數為 dp[i][j]。

2、找出關係數組元素間的關係式

第一種：如果我們 word1[i] 與 word2 [j] 相等，這個時候不需要進行任何操作，所以 dp[i][j] = dp[i-1][j-1]。

第二種：如果我們 word1[i] 與 word2 [j] 不相等，這個時候我們就必須進行調整，而調整的操作有 3 種，我們要選擇一種。
三種操作對應的關係式如下（注意字符串與字符的區別）：

（1）、如果把字符 word1[i] 替換成與 word2[j] 相等，則有 dp[i][j] = dp[i-1][j-1] + 1;

（2）、如果在字符串 word1末尾插入一個與 word2[j] 相等的字符，則有 dp[i][j] = dp[i][j-1] + 1;

（3）、如果把字符 word1[i] 刪除，則有 dp[i][j] = dp[i-1][j] + 1;

所以應該選擇一種操作，使得 dp[i][j] 的值最小，顯然關係式有：dp[i][j] = min(dp[i-1] [j-1]，dp[i][j-1]，dp[i-1][j]) + 1;

3、找出初始值

當 dp[i][j] 中，如果 i 或者 j 有一個為 0，那麼還能使用關係式嗎？答是不能的，因為這個時候把 i - 1 或者 j - 1，就變成負數了，數組就會出問題了，所以我們的初始值是計算出所有的 dp[0][0….n] 和所有的 dp[0….m][0]。

這個還是非常容易計算的，因為當有一個字符串的長度為 0 時，轉化為另外一個字符串，那就只能一直進行插入或者刪除操作了。

時間複雜度：O(mn)
空間複雜度：O(mn)

class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m=len(word1)+1
n=len(word2)+1
dp = [ n*[_] for _ in range(m) ]
for i in range(1,m):
dp[i][0]=dp[i-1][0]+1

for i in range(1,n):
dp[0][i]=dp[0][i-1]+1

for i in range(1,m):
for j in range(1,n):
if word1[i-1]==word2[j-1]:
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
# print(dp)
# print(dp[-1][-1])
return dp[m-1][n-1]

???題解四|動態規劃優化：

定義額外變量 pre = (i-1,j-1) 的值
二維的dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1
轉換為一維的dp[i]=min(dp[i-1],pre,dp[i])+1

空間複雜度：O(n)

class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m=len(word1)+1
n=len(word2)+1
dp = n*[0]

for i in range(0,n):
dp[i]=i

for i in range(1,m):
tmp=dp[0]
dp[0]=i
for j in range(1,n):
pre=tmp
tmp=dp[j]
if word1[i-1]==word2[j-1]:
dp[j]=pre
else:
dp[j]=min(dp[j-1],pre,dp[j])+1
return dp[n-1]

91.解碼方法

連結：https://leetcode-cn.com/problems/decode-ways/

一條包含字母 A-Z 的消息通過以下方式進行了編碼：

'A' -> 1
'B' -> 2
...
'Z' -> 26
給定一個只包含數字的非空字符串，請計算解碼方法的總數。

示例 1:

輸入: "12"
輸出: 2
解釋: 它可以解碼為 "AB"（1 2）或者 "L"（12）。
示例 2:

輸入: "226"
輸出: 3
解釋: 它可以解碼為 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

題解一|動態規劃：
   此題類似於青蛙跳臺階問題，不同的只是多了很多限制條件。

青蛙跳臺階時，可以選擇跳一級，也可以選擇跳兩級，所以青蛙到達第 n 級的臺階有兩種方式：
一種是從第 n-1 級跳上來；
一種是從第 n-2 級跳上來；

解碼也同理，最大編碼為26，所以第 n 個位置編碼的總數也有兩種方式：
一種是從第 n-1 編碼位置的總數；
一種是從第 n-2 編碼位置的總數；

1、定義數組元素的含義
第 i 位置的編碼總數有 dp[i] 個
d[i]代表第i個位置解碼方法的總數

2、找出關係數組元素間的關係式
d[i]=d[i-1]+d[i-2]
d[i+1]=d[i]+d[i-1]

3、找出初始值
dp[0]=1
dp[1]=1
dp[2]=2(此題限制2不好，因為『10』返回1，』27『返回0)

4、限制條件
字符串以『0』開頭時返回0
字符串含有『00』時返回0
字符串中s[i]='0'但是int(s[i-1])>2時返回0
字符串s[i-1:i]>26時，此時應該分開計算。dp[i]+=dp[i-1]

class Solution:
def numDecodings(self, s: str) -> int:

if s[0]=='0' or s is None:
return 0
if len(s)==1:
return 1
if len(s)==2:
return 2

dp=[0]*(len(s))
dp[0]=1
dp[1]=1
dp[2]=2
for i in range(2,len(s)):
if s[i] != '0':
print(i)
dp[i]+=dp[i-1]
if s[i-1] =='1' and (s[i-1]=='2' or s[i]<=6):
dp[i]+=dp[i-2]
if s[i]=='0' and s[i-1]=='0':
return 0
return dp[-1]

用例『10』這個例子預期輸出應該是1,但是實際輸出為2，所以for循環從2開始有問題。
即使改成如下也有問題：
if s=='10' or s=='20':
return 1
elif int(s)>26:
return 0
elif len(s)==2:
return 2

class Solution:
def numDecodings(self, s: str) -> int:

if s[0]=='0' or s is None:
return 0
if len(s)==1:
return 1

length=len(s)
dp=[0]*(length+1)
dp[0]=1
dp[1]=1

for i in range(1,len(s)):
if s[i] != '0':
dp[i+1]+=dp[i]
if s[i-1] =='1' or (s[i-1]=='2' and int(s[i])<=6):
dp[i+1]+=dp[i-1]
if s[i]=='0' and s[i-1]=='0':
return 0
# print(dp[-1])
return dp[length]

?95. 不同的二叉搜索樹 II

連結：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

給定一個整數 n，生成所有由 1 ... n 為節點所組成的二叉搜索樹。

示例:

輸入: 3
輸出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解釋:
以上的輸出對應以下 5 種不同結構的二叉搜索樹：

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

題解一|遞歸：

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n:
return self.build(1,n)
else:
[]
def build(self,start,end):
# 結束條件
if start>end:
return [None,]

trees=[]
for i in range(start,end+1):
leftTrees=self.build(start,i-1)
rightTrees=self.build(i+1,end)
for l in leftTrees:
for r in rightTrees:
currentTree=TreeNode(i)
currentTree.left=l
currentTree.right=r
trees.append(currentTree)
# print(trees)
return trees

96.不同的二叉搜索樹

連結：https://leetcode-cn.com/problems/unique-binary-search-trees/

給定一個整數 n，求以 1 ... n 為節點組成的二叉搜索樹有多少種？

示例:

輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結構的二叉搜索樹:

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

題解一|動態規劃:

二叉樹定義：

二叉查找樹（Binary Search Tree），（又：二叉搜索樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；它的左、右子樹也分別為二叉排序樹。

參考：https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode/
方法：

給定一個有序序列 1 ... n，為了根據序列構建一棵二叉搜索樹。我們可以遍歷每個數字 i，將該數字作為樹根，1 ... (i-1) 序列將成為左子樹，(i+1) ... n 序列將成為右子樹。於是，我們可以遞歸地從子序列構建子樹。
在上述方法中，由於根各自不同，每棵二叉樹都保證是獨特的。

可見，問題可以分解成規模較小的子問題。因此，我們可以存儲並復用子問題的解，而不是遞歸的（也重複的）解決這些子問題，這就是動態規劃法。

函數定義：

令G(n)的從1到n可以形成二叉搜索樹個數
令f(i)為以i為根的二叉搜索樹的個數

所以G(n)是解決問題的函數：G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)

1、定義數組元素的含義
   G[i]代表二叉搜索樹的個數
2、找出數組之間的的關係式
   以i為根，[0,i-1]為左節點，[i+1,n]為右節點
   之後再對[0,i-1]和[i+1,n]遞歸求解

f(i)=G(i-1)+G(n-i)
G(n)=f(1) + f(2) + f(3) + f(4) + ... + f(n)
=G(0)G(n-1)+G(1)G(n-2)+...+G(n-1)G(0)

3、找出初始值
   G[0]=1
   G[1]=1
   G[2]=2

class Solution:
def numTrees(self, n: int) -> int:
dp=[0]*(n+1)
dp[0]=1
dp[1]=1

for i in range(2,n+1):
for j in range(1,i+1):
dp[i]+=dp[j-1]*dp[i-j]
# print(dp)
return dp[n]

118.楊輝三角

連結：https://leetcode-cn.com/problems/pascals-triangle/

給定一個非負整數 numRows，生成楊輝三角的前 numRows 行。

在楊輝三角中，每個數是它左上方和右上方的數的和。

示例:

輸入: 5
輸出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

題解一：

class Solution:
def generate(self, numRows: int) -> List[List[int]]:
triangle=[]
for i in range(numRows):
row=[None for _ in range(i+1)]
row[0],row[-1]=1,1
for j in range(1,len(row)-1):
row[j]=triangle[i-1][j-1]+triangle[i-1][j]
triangle.append(row)
return triangle

題解二|動態規劃：

1、定義數組元素的含義
dp存儲每個數

2、找出數組之間的的關係式
遍歷dp，將為0的位置使用動態規劃填入，公式：dp[i][j]=dp[i-1][j-1]+dp[i-1][j]

3、找出初始值
初始化結果數組，numRows表示結果數組dp的行數，每一行的元素個數等於所處第幾行。全部初始化為0；
將邊界全部初始化為1；

時間複雜度：O(n^2)，等差數列求和。
空間複雜度：O(n^2)，等差數列求和。

class Solution:
def generate(self, numRows: int) -> List[List[int]]:
dp=[[0]*i for i in range(1,numRows+1)]
for i in range(numRows):
dp[i][0]=dp[i][-1]=1
for i in range(0,numRows):
for j in range(i+1):
if dp[i][j]==0:
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
return dp

119. 楊輝三角 II

連結：https://leetcode-cn.com/problems/pascals-triangle-ii/

給定一個非負索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。

在楊輝三角中，每個數是它左上方和右上方的數的和。

示例:

輸入: 3
輸出: [1,3,3,1]
進階：你可以優化你的算法到 O(k) 空間複雜度嗎？

題解一|動態規劃：

class Solution:
def getRow(self, rowIndex: int) -> List[int]:
dp=[[0]* i for i in range(1,rowIndex+2)]
for i in range(rowIndex+1):
dp[i][0]=dp[i][-1]=1
for i in range(rowIndex+1):
for j in range(i+1):
if dp[i][j]==0:
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
return dp[rowIndex]

120.三角形最小路徑和

連結：https://leetcode-cn.com/problems/triangle/

給定一個三角形，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結點上。

例如，給定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。

說明：

如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數）來解決這個問題，那麼你的算法會很加分。

題解一|動態規劃：

1、定義數組的含義

dp[i][j]為最小路徑和

2、找出遞推關係式

從第二行開始，遍歷區間[1,n):
對每一層的元素進行遍歷，遍歷區間[0,len(triangle[i])，存在3種情況：
首位；
末位；
其他元素；

3、找到初始值

class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if triangle is None:
return 0
m=len(triangle)
# print(triangle,m,triangle[0]) # m=4,triangle[0]=[2]
if m==1:
return triangle[0][0]
dp=triangle
for i in range(1,m):
for j in range(len(triangle[i])):
if j==0:
dp[i][j]=triangle[i-1][j]+triangle[i][j]
elif j== len(triangle[i])-1:
dp[i][j]=triangle[i-1][j-1]+triangle[i][j]
else:
dp[i][j]=min(triangle[i-1][j],triangle[i-1][j-1])+triangle[i][j]
return min(dp[-1])

優化一下，空間複雜度變為O(n).

class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if triangle is None:
return 0
m=len(triangle)
if m==1:
return triangle[0][0]
for i in range(1,m):
for j in range(len(triangle[i])):
if j==0:
triangle[i][j]+=triangle[i-1][j]
elif j== len(triangle[i])-1:
triangle[i][j]+=triangle[i-1][j-1]
else:
triangle[i][j]+=min(triangle[i-1][j],triangle[i-1][j-1])
return min(triangle[-1]) # 返回最後一行的最小值

139.單詞拆分

連結：https://leetcode-cn.com/problems/word-break/

給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個或多個在字典中出現的單詞。

說明：

拆分時可以重複使用字典中的單詞。
你可以假設字典中沒有重複的單詞。
示例 1：

輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因為 "leetcode" 可以被拆分成 "leet code"。
示例 2：

輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因為 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重複使用字典中的單詞。
示例 3：

輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false

題解一|動態規劃：

1、定義數組的含義

dp=[False,...,false],長度為n+1，n為字符串長度。
dp[i]表示s的前i位是否可以用wordDict中的單詞表示。

2、找出遞推關係式

遍歷字符串的所有子串，遍歷開始索引i，遍歷區間[0,n)：
遍歷結束索引j，遍歷區間[i+1,n+1)：
若dp[i]=True且s[i,⋯,j)在wordlist中：dp[j]=True

解釋：dp[i]=True說明s的前i位可以用wordDict表示，則s[i,⋯,j)出現在wordDict中，說明s的前j位可以表示。

返回dp[n]

3、找到初始值

初始化dp[0]=True，空字符可以被表示。

時間複雜度：O(n^2)
空間複雜度：O(n)

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n=len(s)
dp=(n+1)*[False]
dp[0]=True
for i in range(n):
for j in range(i+1,n+1):
if dp[i] and s[i:j] in wordDict:
dp[j]=True
# return dp[n]
return dp[-1]

題解二|DFS|記憶化遞歸：

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
memo=[None] * len(s)
def dfs(first):
if first >= len(s):
return True
if memo[first] != None:
return memo[first]

for i in range(first,len(s)):
if s[first:i+1] in wordDict and dfs(i+1):
memo[first]=True
return True
memo[first]=False
return False

return dfs(0)

??題解三|記憶化回溯）:

1、使用記憶化函數，保存出現過的backtrack(s)，避免重複計算。

2、定義回溯函數backtrack(s)

若s長度為0，則返回True，表示已經使用wordDict中的單詞分割完。
初試化當前字符串是否可以被分割res=False
遍歷結束索引i，遍歷區間[1,n+1)：
若s[0,⋯,i−1]在wordDict中：res=backtrack(s[i,...,n-1]) or res。
解釋：保存遍歷結束索引中，可以使字符串切割完成的情況。
返回res

3、返回backtrack(s)

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
import functools
@functools.lru_cache(None)
def back_track(s):
if (not s):
return True
res=False
for i in range(1,len(s)+1):
if(s[:i] in wordDict):
res=back_track(s[i:]) or res
return res
return back_track(s)

題解四|BFS|超時：

import collections

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
visited=[False]*len(s)
queue=collections.deque()
queue.append(0)

while queue:
i=queue.popleft()
if visited[i]:
continue
else:
visited[i]=False

for j in range(i,len(s)):
if s[i:j+1] in wordDict:
if j == len(s)-1:
return True
else:
queue.append(j+1)
return False

152.乘積最大的連續子序列

連結：https://leetcode-cn.com/problems/maximum-product-subarray/

給定一個整數數組 nums ，找出一個序列中乘積最大的連續子序列（該序列至少包含一個數）。

示例 1:

輸入: [2,3,-2,4]
輸出: 6
解釋: 子數組 [2,3] 有最大乘積 6。
示例 2:

輸入: [-2,0,-1]
輸出: 0
解釋: 結果不能為 2, 因為 [-2,-1] 不是子數組。

題解一|動態規劃:

此題類似於52題最大子序和，唯一的區別是：由於存在負數，那麼會導致最大的變最小的，最小的變最大的，因此還需要維護當前最小值minTmp，minTmp = min(minTmp * nums[i], nums[i])

1、定義數組元素的含義

dp[i]為以num[i]結尾的子段的最大子段乘積
dp[1]為以num[1]結尾的最大子段乘積

2、尋找遞推表達式

只考慮第一個元素，則最大子段和為其本身 dp[0] = nums[0]

考慮前兩個元素，最大子段和為 nums[0],num[1]以及 nums[0]*num[1] 中最大值 設為dp[1]

考慮前三個元素，如何求其最大子段乘積？還是分為兩種情況討論，第三個元素在最後的字串內嗎？

若第三個元素也包含在最後的字串內，則dp[2] = Max(dp[1]*nums[2] , nums[2])

dp[i]=max(dp[i-1]*num[i],num[i])
由於存在負數：
dp_[i]=min(dp_[i-1]*num[i],num[i])

3、找出初始值

dp[0]=num[0]
dp[1]=max(dp[0]* num[1],num[1])

class Solution:
def maxProduct(self, nums: List[int]) -> int:
lens=len(nums)
if lens==0:
return 0
dp=lens*[0]
mindp=lens*[0]
dp[0]=nums[0]
mindp[0]=nums[0]
res=nums[0]
for i in range(1,lens):
dp[i]=max(dp[i-1]*nums[i],nums[i],mindp[i-1]*nums[i])
mindp[i]=min(dp[i-1]*nums[i],nums[i],mindp[i-1]*nums[i])
res=max(res,dp[i])
return res

class Solution:
def maxProduct(self, nums: List[int]) -> int:
lens=len(nums)
if lens==0:
return 0
res=float('-inf')
maxTmp=1
minTmp=1
for i in range(lens):
if nums[i]<0:
maxTmp,minTmp=minTmp,maxTmp
maxTmp=max(maxTmp*nums[i],nums[i])
minTmp=min(minTmp*nums[i],nums[i])

res=max(res,maxTmp)
return res

221.最大正方形

連結：https://leetcode-cn.com/problems/maximal-square/

在一個由 0 和 1 組成的二維矩陣內，找到只包含 1 的最大正方形，並返回其面積。

示例:

輸入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

輸出: 4

題解一|動態規劃：

1、定義數組元素的含義

dp[i][j]表示以(i,j)為右下角，且只包含1的正方形邊長最大值;
計算出所有 dp(i,j) 的值，那麼其中的最大值即為矩陣中只包含 1 的正方形的邊長最大值，其平方即為最大正方形的面積。

2、尋找遞推表達式

如果該位置的值是 0，則 dp(i,j)=0，因為當前位置不可能在由 1 組成的正方形中；

如果該位置的值是 1，則 dp(i,j) 的值由其上方、左方和左上方的三個相鄰位置的 dp值決定。具體而言，當前位置的元素值等於三個相鄰位置的元素中的最小值加 1，狀態轉移方程如下：

dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1

3、找出初始值

if matrix[i][j]=='1':
if i==0 or j==0:
dp[i][j]=1

class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if len(matrix)==0 or len(matrix[0])==0:
return 0
maxSide=0
rows,columns=len(matrix),len(matrix[0])
dp=[[0]*columns for _ in range(rows)]
for i in range(rows):
for j in range(columns):
if matrix[i][j]=='1':
if i==0 or j==0:
dp[i][j]=1
else:
dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
maxSide=max(maxSide,dp[i][j])
maxSquare=maxSide*maxSide
return maxSquare

264. 醜數 II

連結：https://leetcode-cn.com/problems/ugly-number-ii/

編寫一個程序，找出第 n 個醜數。

醜數就是質因數隻包含 2, 3, 5 的正整數。

示例:

輸入: n = 10
輸出: 12
解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個醜數。
說明:

1 是醜數。
n 不超過1690。

題解一|動態規劃+3個指針:

class Solution:
def nthUglyNumber(self, n: int) -> int:
nums=[1]
i2=i3=i5=0
for i in range(1,n):
ugly=min(nums[i2]*2,nums[i3]*3,nums[i5]*5)
nums.append(ugly)
if ugly == nums[i2]*2:
i2+=1
if ugly == nums[i3]*3:
i3+=1
if ugly== nums[i5]*5:
i5+=1
return nums[n-1]

279. 完全平方數

連結：https://leetcode-cn.com/problems/perfect-squares/

給定正整數 n，找到若干個完全平方數（比如 1, 4, 9, 16, ...）使得它們的和等於 n。你需要讓組成和的完全平方數的個數最少。

示例 1:

輸入: n = 12
輸出: 3
解釋: 12 = 4 + 4 + 4.
示例 2:

輸入: n = 13
輸出: 2
解釋: 13 = 4 + 9.

題解一|動態規劃：

1、定義數組元素的含義

dp[i]表示i最少可以由幾個平方數構成

2、尋找遞推表達式

遍歷dp，對於i，遍歷區間[2,n+1)：
遍歷所有平方數小於i的數j，遍歷區間[1,int(\sqrt{i})+1):
dp[i]=min(dp[i],dp[i-j*j]+1)
始終保存所有可能情況中的最小值
返回dp[n]

3、找出初始值
   dp=[0,1,2,…,n]，長度為n+1，最多次數就是全由1構成。

時間複雜度：O(n\sqrt{n})
空間複雜度：O(n)

import math
class Solution:
def numSquares(self, n: int) -> int:
dp=[i for i in range(n+1)]
for i in range(2,n+1):
for j in range(1,int(math.sqrt(i))+1): # 開方也可使用i**0.5
dp[i]=min(dp[i],dp[i-j*j]+1)
return dp[n]

題解二|廣度優先遍歷bfs：

藉助隊列實現廣度優先遍歷（層次遍歷）:

1、初始化隊列queue=[n]，訪問元組visited={}，初試化路徑長度step=0
2、特判，若n==0，返回0。
3、循環條件，隊列不為空：

step+=1，因為循環一次，意味著一層中的節點已經遍歷完，所以路徑長度需要加一。
定義當前層中的節點數length=len(queue)，遍歷當前層的所有節點：
令tmp為隊首元素。
遍歷所有可能數i的平方數，遍歷區間[1,int(\sqrt{tmp})+1)：
定義x=tmp-i^2
若x==0，返回當前的路徑長度。
若x not in visited，表示當前節點未出現過：將該節點入隊並在訪問數組中加入。
4、返回step

時間複雜度：O(n*\sqrt{n})，並不準確
空間複雜度：O(n)

from collections import deque
class Solution:
def numSquares(self, n: int) -> int:
if n==0:
return 0
queue=deque([n])
visited=set()
step=0
while queue:
step+=1
length=len(queue)
for _ in range(length):
tmp=queue.pop()
for j in range(1,int(tmp**0.5)+1):
node=tmp-j**2
if node==0:
return step
if node not in visited:
queue.appendleft(node)
visited.add(node)
return step

繼續理解 300. 最長上升子序列

連結：https://leetcode-cn.com/problems/longest-increasing-subsequence/

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

示例:

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

可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可。
你算法的時間複雜度應該為 O(n^2) 。
進階: 你能將算法的時間複雜度降低到 O(n*logn) 嗎?

題解一|動態規劃：

1、定義數組元素的含義

定義 dp[i] 為考慮前 i 個元素，以第 i 個數字結尾的最長上升子序列的長度，注意 nums[i] 必須被選取。

2、尋找遞推表達式

從小到大計算 dp[] 數組的值，在計算 dp[i] 之前，我們已經計算出 dp[0…i−1] 的值:
dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]

3、找出初始值
   dp[i]=1，1 個字符顯然是長度為 1 的上升子序列。

時間複雜度：O(n^2)，其中 n 為數組 nums 的長度。動態規劃的狀態數為 n，計算狀態 dp[i] 時，需要 O(n) 的時間遍歷 dp[0…i−1] 的所有狀態，所以總時間複雜度為 O(n^2)
空間複雜度：O(n)，需要額外使用長度為 n 的 dp 數組。

class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
dp=[]
for i in range(len(nums)):
dp.append(1)
for j in range(i):
if nums[i]>nums[j]:
dp[i]=max(dp[i],dp[j]+1)
return max(dp)

題解二|動態規劃+二分查找：

1、定義數組元素的含義

tails[k] 的值代表 長度為 k+1 子序列 的尾部元素值。

2、尋找遞推表達式

設 res 為 tails 當前長度，代表直到當前的最長上升子序列長度。設 j∈[0,res)，考慮每輪遍歷 nums[k] 時，通過二分法遍歷 [0,res) 列表區間，找出 nums[k]的大小分界點，會出現兩種情況：

區間中存在 tails[i] > nums[k] ：將第一個滿足 tails[i] > nums[k]執行 tails[i] = nums[k] ；因為更小的 nums[k]後更可能接一個比它大的數字。

區間中不存在 tails[i] > nums[k] ：意味著 nums[k]可以接在前面所有長度的子序列之後，因此肯定是接到最長的後面（長度為 res），新子序列長度為 res + 1。

3、找出初始值
   tails[i]=0，tails 列表所有值 =0。

4、返回 res ，即最長上升子子序列長度。

時間複雜度 O(NlogN) ：遍歷 nums 列表需 O(N)，在每個 nums[i] 二分法需 O(logN)
空間複雜度 O(N) ：tails 列表佔用線性大小額外空間。

class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
tails,res=[0]*len(nums),0
for num in nums:
i,j=0,res
while i<j:
m=(i+j)//2
if tails[m]<num:
i=m+1
else:
j=m
tails[i]=num
if j==res:
res+=1
return res

https://mp.weixin.qq.com/s/02o_OPgePjaz3dXnw9TA1w

303. 區域和檢索 - 數組不可變

連結：https://leetcode-cn.com/problems/range-sum-query-immutable/

給定一個整數數組 nums，求出數組從索引 i 到 j (i ≤ j) 範圍內元素的總和，包含 i, j 兩點。

示例：

給定 nums = [-2, 0, 3, -5, 2, -1]，求和函數為 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
說明:

你可以假設數組不可變。
會多次調用 sumRange 方法。

題解一|暴力：

缺點：每次調用sumRange都要重新進行計算

class NumArray:

def __init__(self, nums: List[int]):
self.nums=nums

def sumRange(self, i: int, j: int) -> int:
sum=0
for each in range(i,j+1):
sum+=self.nums[each]
return sum

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

題解二|緩存+動態規劃：

class NumArray:

def __init__(self, nums: List[int]):
self.nums=nums
if not nums:
return
n=len(nums)
self.dp=[0]*(n+1)
self.dp[1]=nums[0]
for i in range(2,n+1):
self.dp[i]=self.dp[i-1]+nums[i-1]

def sumRange(self, i: int, j: int) -> int:
return self.dp[j+1]-self.dp[i]

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

class NumArray:

def __init__(self, nums: List[int]):
self.nums=nums
if not nums:
return
n=len(nums)
self.dp=[0]*(n+1)
for i in range(0,n):
self.dp[i+1]=self.dp[i]+nums[i]
# print(self.dp)

def sumRange(self, i: int, j: int) -> int:
return self.dp[j+1]-self.dp[i]

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

304. 二維區域和檢索 - 矩陣不可變

連結：https://leetcode-cn.com/problems/range-sum-query-2d-immutable/

給定一個二維矩陣，計算其子矩形範圍內元素的總和，該子矩陣的左上角為 (row1, col1) ，右下角為 (row2, col2)。

Range Sum Query 2D
上圖子矩陣左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，該子矩形內元素的總和為 8。

示例:

給定 matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
說明:

你可以假設矩陣不可變。
會多次調用 sumRegion 方法。
你可以假設 row1 ≤ row2 且 col1 ≤ col2。

題解一|動態規劃：

sum(abcd)=sum(od)−sum(ob)−sum(oc)+sum(oa)

1、定義數組的含義

dp[i][j]表示矩陣左上角到matrix[i][j]的累加和

class NumMatrix:

def __init__(self, matrix: List[List[int]]):

if not matrix or not matrix[0]:pass
else:
row = len(matrix)
col = len(matrix[0])
self.dp = [[ 0 ] * (col + 1) for _ in range(row + 1)]
# 求行的前綴和
for i in range(1, row + 1):
for j in range(1 ,col + 1):
self.dp[i][j] = self.dp[i][j - 1] + matrix[i - 1][j - 1]
# 求列的前綴和
for j in range(1, col + 1):
for i in range(1, row + 1):
self.dp[i][j] += self.dp[i - 1][j]
# print(self.dp)

def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return self.dp[row2 + 1][col2 + 1] - self.dp[row1][col2 + 1] - self.dp[row2 + 1][col1] + self.dp[row1][col1]

# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

class NumMatrix:

def __init__(self, matrix: List[List[int]]):

if not matrix or not matrix[0]:pass
else:
row = len(matrix)
col = len(matrix[0])
self.dp = [[ 0 ] * (col + 1) for _ in range(row + 1)]

for i in range(1, row + 1):
for j in range(1, col + 1):
self.dp[i][j] = matrix[i - 1][j - 1] + self.dp[i - 1][j] + self.dp[i][j - 1] - self.dp[i-1][j-1] # [i-1, j-1]重複計算了, 所以需要減去.

def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return self.dp[row2 + 1][col2 + 1] - self.dp[row1][col2 + 1] - self.dp[row2 + 1][col1] + self.dp[row1][col1]

# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

338. 比特位計數

連結：https://leetcode-cn.com/problems/counting-bits/

給定一個非負整數 num。對於 0 ≤ i ≤ num 範圍中的每個數字 i ，計算其二進位數中的 1 的數目並將它們作為數組返回。

示例 1:

輸入: 2
輸出: [0,1,1]
示例 2:

輸入: 5
輸出: [0,1,1,2,1,2]
進階:

給出時間複雜度為O(n*sizeof(integer))的解答非常容易。但你可以在線性時間O(n)內用一趟掃描做到嗎？
要求算法的空間複雜度為O(n)。
你能進一步完善解法嗎？要求在C++或任何其他語言中不使用任何內置函數（如 C++ 中的 __builtin_popcount）來執行此操作。

題解一（動態規劃）：

1、定義數組含義

dp[i]表示數字i計算其二進位數中的 1 的數目。

2、找出數組遞推關係式

當i為奇數時：
奇數一定比前面那個偶數多一個 1，因為多的就是最低位的 1。
當i為偶數時：
二進位是逢2開始進位的，也就是在偶數的時候，一個偶數相當一另一個數成以2得到，在二進位運算中，就是左移一位，也就是在低位多加1個0，故遇到偶數的時候就是dp[i] = dp[i/2]。

3、找到初始值

dp[0]=0
dp[1]=1

時間複雜度：O(n)
空間複雜度：O(n)

class Solution:
def countBits(self, num: int) -> List[int]:
if num==0:
return [0]
dp=[0]*(num+1)
dp[0]=0
dp[1]=1
for i in range(2,num+1):
if i%2==0:
dp[i]=dp[i//2]
else:
dp[i]=dp[i-1]+1
return dp

343. 整數拆分

連結：https://leetcode-cn.com/problems/integer-break/

給定一個正整數 n，將其拆分為至少兩個正整數的和，並使這些整數的乘積最大化。返回你可以獲得的最大乘積。

示例 1:

輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
說明: 你可以假設 n 不小於 2 且不大於 58。

題解一|動態規劃

1、定義數組

dp[i]代表i拆分後的最大乘積

2、遞推表達式

dp[i]=max(dp[i],j*(i-j),j*dp[i-j])

(i - j) * j 代表的是整數 i 拆分成 2 部分, 分別為 (i - j) * j；

j * dp[i - j]代表的是整數 i 拆 2 部分以上， dp[i - j] 就是代表在之前的動態規劃求得的整數 i - j 的分割最大的乘積

3、初始值
   dp[i]=1，從3開始。

class Solution:
def integerBreak(self, n: int) -> int:
dp=[1 for i in range(n+1)]
for i in range(3,n+1):
for j in range(1,i):
dp[i]=max(dp[i],j*(i-j),j*dp[i-j])
return dp[n]

354. 俄羅斯套娃信封問題

連結：https://leetcode-cn.com/problems/russian-doll-envelopes/

給定一些標記了寬度和高度的信封，寬度和高度以整數對形式 (w, h) 出現。當另一個信封的寬度和高度都比這個信封大的時候，這個信封就可以放進另一個信封裡，如同俄羅斯套娃一樣。

請計算最多能有多少個信封能組成一組「俄羅斯套娃」信封（即可以把一個信封放到另一個信封裡面）。

說明:
不允許旋轉信封。

示例:

輸入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
輸出: 3
解釋: 最多信封的個數為 3, 組合為: [2,3] => [5,4] => [6,7]。

題解一|動態規劃|超時

class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
if not envelopes:
return 0
envelopes=sorted(envelopes,key=lambda x:(x[0],-x[1]))
dp=[1]*len(envelopes)
count=1
for i in range(len(envelopes)):
for j in range(i):
if envelopes[i][1] > envelopes[j][1] and dp[j]+1 > dp[i]:
dp[i]=dp[j]+1
count=max(count,dp[i])
return count

稍微修改下，通過：

class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
if not envelopes:
return 0
envelopes=sorted(envelopes,key=lambda x:(x[0],-x[1]))
dp=[1]*len(envelopes)
for i in range(len(envelopes)):
for j in range(i):
if envelopes[i][1] > envelopes[j][1] and dp[j]+1 > dp[i]:
dp[i]=max(dp[i],dp[j]+1)
return max(dp)

357. 計算各個位數不同的數字個數

連結：https://leetcode-cn.com/problems/count-numbers-with-unique-digits/

給定一個非負整數 n，計算各位數字都不同的數字 x 的個數，其中 0 ≤ x < 10^n 。

示例:

輸入: 2
輸出: 91
解釋: 答案應為除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 區間內的所有數字。

題解一|動態規劃:

數字一共有0~9十個，所以n超過十位一定會重複。

1位 10
2位 9*9+10 （第一位不能0）
3位 9*9*8+9*9+10
4位 9*9*8*7+9*9*8+9*9+10
...
i位 dp1[i] = dp2[i-1]*(10-(i-1))+dp1[i-1] （i從2開始，dp1[1] = 10, dp2[1] = 9）

class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
if n==0:
return 1
dp1=[0]*(n+1)
dp2=[0]*(n+1)
dp1[1]=10
dp2[1]=9
for i in range(2,min(11,n+1)):
dp2[i]=dp2[i-1]*(10-(i-1))
dp1[i]=dp2[i]+dp1[i-1]
if n>=11:
return dp[10]
return dp1[n]

class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
if n==0:
return 1
fisrt,second=10,9*9
size=min(n,10)
for i in range(2,size+1):
fisrt+=second
second*=(10-i)
return fisrt

??題解二|回溯：

class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
used=[False]*10
def backtrace(first,used):
count=0
if first != n:
for i in range(10):
# 剪枝：多位數時，第一個數字不能為0
if i==0 and n>1 and first==1:
continue
if used[i]:
continue
used[i]=True
count+=backtrace(first+1,used)+1
used[i]=False
return count
if not n:
return 1
return backtrace(0,used)

368. 最大整除子集

連結：https://leetcode-cn.com/problems/largest-divisible-subset/

給出一個由無重複的正整數組成的集合，找出其中最大的整除子集，子集中任意一對 (Si，Sj) 都要滿足：Si % Sj = 0 或 Sj % Si = 0。

如果有多個目標子集，返回其中任何一個均可。

示例 1:

輸入: [1,2,3]
輸出: [1,2] (當然, [1,3] 也正確)
示例 2:

輸入: [1,2,4,8]
輸出: [1,2,4,8]

題解一|動態規劃：

1、sorted()排序；
2、dp[i]表示以下標i位置元素結尾得最長序列。
3、遍歷0-(i-1)，如果nums[i]整除nums[j]，則判斷dp[i]和dp[j] + 1哪個大

class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
if not nums:
return []
nums=sorted(nums)
dp=[[i] for i in nums]
res=[]
for i in range(0,len(nums)):
for j in range(0,i):
if nums[i]%nums[j]==0:
if len(dp[i])<len(dp[j]+[nums[i]]):
dp[i]=dp[j]+[nums[i]]
if len(dp[i])>len(res):
res=dp[i]
return res

392. 判斷子序列

連結：https://leetcode-cn.com/problems/is-subsequence/

給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。

你可以認為 s 和 t 中僅包含英文小寫字母。字符串 t 可能會很長（長度 ~= 500,000），而 s 是個短字符串（長度 <=100）。

字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩餘字符相對位置形成的新字符串。（例如，"ace"是"abcde"的一個子序列，而"aec"不是）。

示例 1:
s = "abc", t = "ahbgdc"

返回 true.

示例 2:
s = "axc", t = "ahbgdc"

返回 false.

後續挑戰 :

如果有大量輸入的 S，稱作S1, S2, ... , Sk 其中 k >= 10億，你需要依次檢查它們是否為 T 的子序列。在這種情況下，你會怎樣改變代碼？

題解一|雙指針：

class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
p,q=0,0
count=0
while p<len(s) and q<len(t):
if s[p]==t[q]:
count+=1
p+=1
q+=1
return p==len(s)

題解二|二分+哈希：

class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
hash={}
for i,word in enumerate(t):
if word not in hash:
hash[word]=[i] # 注意這裡是列表
else:
hash[word].append(i)

index = -1
for word in s:
if word not in hash:
return False
# 字母s出現的索引 用二分法找到其中大於index的第一個
indexes = hash[word]
left = 0
right = len(indexes)
while left < right:
mid = left + (right - left) // 2
if indexes[mid] > index:
right = mid
else:
left = mid + 1
if left == len(indexes):
return False
index = indexes[left]

return True

516. 最長回文子序列

給定一個字符串 s ，找到其中最長的回文子序列，並返回該序列的長度。可以假設 s 的最大長度為 1000 。

示例 1:
輸入:

"bbbab"
輸出:

4
一個可能的最長回文子序列為 "bbbb"。

示例 2:
輸入:

"cbbd"
輸出:

2
一個可能的最長回文子序列為 "bb"。

提示：

1 <= s.length <= 1000
s 只包含小寫英文字母

題解一|動態規劃：

1、dp 數組的定義是：在子串s[i..j]中，最長回文子序列的長度為dp[i][j]

2、狀態轉移方程

if (s[i] == s[j])
// 它倆一定在最長回文子序列中
dp[i][j] = dp[i + 1][j - 1] + 2;
else
// s[i+1..j] 和 s[i..j-1] 誰的回文子序列更長？
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

答案：dp[0][n - 1]，也就是整個s的最長回文子序列的長度。

3、bad case

如果只有一個字符，顯然最長回文子序列長度是 1，也就是dp[i][j] = 1,(i == j)。

因為i肯定小於等於j，所以對於那些i > j的位置，根本不存在什么子序列，應該初始化為 0。

為了保證每次計算dp[i][j]，左、下、左下三個方向的位置已經被計算出來，只能斜著遍歷或者反著遍歷：

class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n=len(s)
dp=[[0]*n for i in range(n)]

for i in range(n):
dp[i][i]=1

# 反著遍歷保證正確的狀態轉移
for i in range(n-1,-1,-1):
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+1][j],dp[i][j-1])
return dp[0][n-1]

651.4鍵鍵盤

如何在 N 次敲擊按鈕後得到最多的 A？

對 dp 數組的不同定義需要完全不同的邏輯，從而產生完全不同的解法。

題解一：

流程：對於動態規劃問題，首先要明白有哪些「狀態」，有哪些「選擇」。

有哪些「選擇」是很明顯的：

4 種，就是題目中提到的四個按鍵，分別是A、C-A、C-C、C-V（Ctrl簡寫為C）。

有哪些「狀態」？或者換句話說，我們需要知道什麼信息，才能將原問題分解為規模更小的子問題？

定義三個狀態行不行：

第一個狀態是剩餘的按鍵次數，用n表示；
第二個狀態是當前屏幕上字符 A 的數量，用a_num表示；
第三個狀態是剪切板中字符 A 的數量，用copy表示。

如此定義「狀態」，就可以知道 base case：當剩餘次數n為 0 時，a_num就是我們想要的答案。

結合剛才說的 4 種「選擇」，我們可以把這幾種選擇通過狀態轉移表示出來：

dp(n - 1, a_num + 1, copy), # A
解釋：按下 A 鍵，屏幕上加一個字符
同時消耗 1 個操作數

dp(n - 1, a_num + copy, copy), # C-V
解釋：按下 C-V 粘貼，剪切板中的字符加入屏幕
同時消耗 1 個操作數

dp(n - 2, a_num, a_num) # C-A C-C
解釋：全選和複製必然是聯合使用的，
剪切板中 A 的數量變為屏幕上 A 的數量
同時消耗 2 個操作數

問題的規模n在不斷減小，肯定可以到達n = 0的 base case，所以這個思路是正確的：

def maxA(n):
def dp(n,a_num,copy):
# 初始值
if n<=0:
return a_num
# 所有選擇全部試一遍，選擇最大結果
return max(
dp(n-1,a_num+1,copy),
dp(n-1,a_num+copy,copy),
dp(n-2,a_num,a_num)
)
return dp(n,0,0) # 可以按n次按鍵，屏幕和剪切板種還沒有A

優化：

def maxA(n):
memo=dict()
def dp(n,a_num,copy):
# 初始值
if n<=0:
return a_num
# 避免計算重疊子問題
if (n,a_num,copy) in demo:
return memo[(n,a_num,copy)]

memo[(n,a_num,copy)]= max(
dp(n-1,a_num+1,copy),
dp(n-1,a_num+copy,copy),
dp(n-2,a_num,a_num)
)
return memo[(n,a_num,copy)]
return dp(n,0,0) # 可以按n次按鍵，屏幕和剪切板種還沒有A

可以把這個 dp 函數寫成 dp 數組：

dp[n][a_num][copy] #狀態的總數（時空複雜度）就是這個三維數組的體積

我們知道變量n最多為N，但是a_num和copy最多為多少我們很難計算，複雜度起碼也有 O(N^3) 吧。

題解二：

「選擇」還是那 4 個，但是這次我們只定義一個「狀態」，也就是剩餘的敲擊次數n。

最優按鍵序列一定只有兩種情況：

要麼一直按A：A,A,…A（當 N 比較小時）。

要麼是這麼一個形式：A,A,…C-A,C-C,C-V,C-V,…C-V（當 N 比較大時）。

因為字符數量少（N 比較小）時，C-A C-C C-V這一套操作的代價相對比較高，可能不如一個個按A；而當 N 比較大時，後期C-V的收穫肯定很大。這種情況下整個操作序列大致是：開頭連按幾個A，然後C-A C-C組合再接若干C-V，然後再C-A C-C接著若干C-V，循環下去。

換句話說，最後一次按鍵要麼是A要麼是C-V。明確了這一點，可以通過這兩種情況來設計算法：

https://mp.weixin.qq.com/s?__biz=Mzg2NzA4MTkxNQ==&mid=2247486045&idx=2&sn=c270733b9ea06403ab9851bbc5d935db&scene=21#wechat_redirect

673. 最長遞增子序列的個數

連結：https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/

給定一個未排序的整數數組，找到最長遞增子序列的個數。

示例 1:

輸入: [1,3,5,4,7]
輸出: 2
解釋: 有兩個最長遞增子序列，分別是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:

輸入: [2,2,2,2,2]
輸出: 5
解釋: 最長遞增子序列的長度是1，並且存在5個子序列的長度為1，因此輸出5。

題解一|動態規劃：

class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
dp=[1]*len(nums)
count=[1]*len(nums)
MAX=0
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
if dp[j]+1 > dp[i]: # 代表第一次遇到最長子序列
dp[i]=max(dp[i],dp[j]+1)
count[i]=count[j]
elif dp[j]+1 == dp[i]: # 代表已經遇到最長子序列
count[i]+=count[j]
MAX = max(MAX, dp[i])
res=0
for i in range(len(nums)):
if dp[i]==MAX:
res+=count[i]
return res

674. 最長連續遞增序列

連結：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/

給定一個未經排序的整數數組，找到最長且連續的的遞增序列，並返回該序列的長度。

示例 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。

題解一|動態規劃：

1、數組定義：dp[i]代表nums[i]值結尾的最長連續遞增序列的長度
2、狀態轉移方程

nums[i]＞nums[i−1]，i至少可以與i-1形成一個連續遞增序列，因為它們倆挨著，並且是遞增的，長度上是dp[i-1]+1

nums[i]＜=nums[i-1],這時候，不能形成連續遞增序列，後一個數要比前一個數小，呈下降的趨勢，注意=不認為是遞增的

3、初始值dp[i]=1

時間複雜度：o(n)
空間複雜度：o(n)

class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
if not nums:
return 0
dp=[1]*len(nums)
for i in range(1,len(nums)):
if nums[i] > nums[i-1]:
dp[i]=max(dp[i],dp[i-1]+1)
return max(dp)

o(1)

public int findLengthOfLCIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int max = 1;
int[] dp = new int[2];
dp[0] = 1;
for (int i = 1; i ＜ n; i++) {
dp[i % 2] = 1;//前一個狀態值都會被覆蓋，需要重新初始化
if (nums[i] ＞ nums[i - 1]) {
dp[i % 2] += dp[(i - 1) % 2];//當前狀態依賴前一狀態，需要再前一狀態上累加
}
max = Math.max(max, dp[i % 2]);
}
return max;
}

746. 使用最小花費爬樓梯

連結：https://leetcode-cn.com/problems/min-cost-climbing-stairs/

數組的每個索引作為一個階梯，第 i個階梯對應著一個非負數的體力花費值 cost[i](索引從0開始)。

每當你爬上一個階梯你都要花費對應的體力花費值，然後你可以選擇繼續爬一個階梯或者爬兩個階梯。

您需要找到達到樓層頂部的最低花費。在開始時，你可以選擇從索引為 0 或 1 的元素作為初始階梯。

示例 1:

輸入: cost = [10, 15, 20]
輸出: 15
解釋: 最低花費是從cost[1]開始，然後走兩步即可到階梯頂，一共花費15。
示例 2:

輸入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
輸出: 6
解釋: 最低花費方式是從cost[0]開始，逐個經過那些1，跳過cost[3]，一共花費6。
注意：

cost 的長度將會在 [2, 1000]。
每一個 cost[i] 將會是一個Integer類型，範圍為 [0, 999]。

題解一|動態規劃：
1、定義
   dp[i]為踏上第i級臺階的最小花費
2、狀態轉移
踏上第i級臺階有兩種方法：

先踏上第i-2級臺階（最小總花費dp[i-2]），再直接邁兩步踏上第i級臺階（花費cost[i]），最小總花費dp[i-2] + cost[i]；

先踏上第i-1級臺階（最小總花費dp[i-1]），再邁一步踏上第i級臺階（花費cost[i]），最小總花費dp[i-1] + cost[i]；

則dp[i]是上面這兩個最小總花費中的最小值。

因此狀態轉移方程是：dp[i] = min(dp[i-2], dp[i-1]) + cost[i]。

3、初始條件：

最後一步踏上第0級臺階，最小花費dp[0] = cost[0]。

最後一步踏上第1級臺階有兩個選擇：

可以分別踏上第0級與第1級臺階，花費cost[0] + cost[1]；
也可以從地面開始邁兩步直接踏上第1級臺階，花費cost[1]。
最小值dp[1] = min(cost[0] + cost[1], cost[1]) = cost[1]。

class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
if not cost:
return 0
dp=[0]*len(cost)
dp[0]=cost[0]
dp[1]=cost[1]
for i in range(2,len(cost)):
dp[i]=min(dp[i-1]+cost[i],dp[i-2]+cost[i])
return min(dp[-1],dp[-2])

1025. 除數博弈

連結：https://leetcode-cn.com/problems/divisor-game/

愛麗絲和鮑勃一起玩遊戲，他們輪流行動。愛麗絲先手開局。

最初，黑板上有一個數字 N 。在每個玩家的回合，玩家需要執行以下操作：

選出任一 x，滿足 0 < x < N 且 N % x == 0 。
用 N - x 替換黑板上的數字 N 。
如果玩家無法執行這些操作，就會輸掉遊戲。

只有在愛麗絲在遊戲中取得勝利時才返回 True，否則返回 false。假設兩個玩家都以最佳狀態參與遊戲。

示例 1：

輸入：2
輸出：true
解釋：愛麗絲選擇 1，鮑勃無法進行操作。
示例 2：

輸入：3
輸出：false
解釋：愛麗絲選擇 1，鮑勃也選擇 1，然後愛麗絲無法進行操作。


提示：

1 <= N <= 1000

題解一|歸納

思路：最後輪到誰時 N=1，那麼誰就是輸家。

假設N為奇數，即 N%2=1:

那麼 N 的約數x一定都是奇數，N-x 一定是偶數；

假設N為偶數，即 N%2=0:

那麼 N 的約數x可能是奇數，也可能是偶數。x為奇數時，N-x為奇數；x為偶數時，N-x為偶數。

題目中說「兩個玩家都以最佳狀態參與遊戲」，並且愛麗絲先手，那她一定會努力讓自己得勝。

結論：

若N是偶數，愛麗絲一定會選x為奇數，讓輪到鮑勃的(N-x)為奇數，這樣她每次都會輪到偶數直至勝利；

若N是奇數，愛麗絲沒得選，只能讓鮑勃輪到的（N-x)為偶數，此時主動權就在鮑勃手中，他會讓愛麗絲每次輪到奇數，直至鮑勃獲勝。

class Solution:
def divisorGame(self, N: int) -> bool:
return N%2==0

題解二|動態規劃

定義：dp[i]為當N=i時，Alice的輸贏

class Solution:
def divisorGame(self, N: int) -> bool:
if N<=1:
return False
dp=[False]* (N+1)
dp[1]= False
dp[2]= True
for i in range(3,N+1):
for j in range(1,i):
if dp[i-j] == False and i%j == 0: # 當dp[i-j]為奇數時，dp[i]為偶數
dp[i]=True
break
return dp[N]

面試題 08.01. 三步問題

連結：https://leetcode-cn.com/problems/three-steps-problem-lcci/

三步問題。有個小孩正在上樓梯，樓梯有n階臺階，小孩一次可以上1階、2階或3階。實現一種方法，計算小孩有多少種上樓梯的方式。結果可能很大，你需要對結果模1000000007。

示例1:

輸入：n = 3
輸出：4
說明: 有四種走法
示例2:

輸入：n = 5
輸出：13
提示:

n範圍在[1, 1000000]之間

題解一|動態規劃

class Solution:
def watiaosToStep(self, n: int) -> int:
if n < 3:
return n
dp=[0]*(n+1)
dp[1]=1
dp[2]=2
dp[3]=4
for i in range(4,n+1):
dp[i]=(dp[i-1]+dp[i-2]+dp[i-3]) % 1000000007
return dp[n]

面試題 16.17. 連續數列

連結：https://leetcode-cn.com/problems/contiguous-sequence-lcci/

給定一個整數數組，找出總和最大的連續數列，並返回總和。

示例：

輸入：[-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子數組 [4,-1,2,1] 的和最大，為 6。
進階：

如果你已經實現複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums)==1:
return nums[0]
dp=[0]*len(nums)
dp[0]=nums[0]
dp[1]=max(dp[0]+nums[1],nums[1])
for i in range(2,len(nums)):
dp[i]=max(dp[i-1]+nums[i],nums[i])
return max(dp)

面試題42. 連續子數組的最大和

連結：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

輸入一個整型數組，數組裡有正數也有負數。數組中的一個或連續多個整數組成一個子數組。求所有子數組的和的最大值。

要求時間複雜度為O(n)。

示例1:

輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。


提示：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums)==1:
return nums[0]
dp=[0]*len(nums)
dp[0]=nums[0]
dp[1]=max(dp[0]+nums[1],nums[1])
for i in range(2,len(nums)):
dp[i]=max(dp[i-1]+nums[i],nums[i])
return max(dp)