問題描述：【DP】120. Triangle
解題思路：
這道題是給一個三角形欺抗，從頂?shù)较掠嬎阕钚÷窂胶汀?/p>
容易想到用動態(tài)規(guī)劃求解，dp[i][j] 存儲累加到位置 (i, j) 的最小路徑和强重。
如果是從頂?shù)较陆食剩敲崔D(zhuǎn)移方程為 dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]，但是會發(fā)現(xiàn)间景，對于第 i 行的在最后一個數(shù)字 dp[i][j]佃声，dp[i-1][j] 不存在（因為第 i-1 行沒有第 j 列）。這樣要判斷邊界倘要，比較麻煩圾亏。
換種思路，可以從底向上封拧，則 dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]志鹃，不會出現(xiàn)越界情況，最后 dp[0] 就是答案泽西。采取從底向上方法時曹铃，注意先初始化最后一行。
Python3 實現(xiàn)：
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
dp = [[0 for col in range(len(triangle[row]))] for row in range(len(triangle))]
for j in range(len(triangle[-1])): # 初始化最后一行
dp[-1][j] = triangle[-1][j]
for i in range(len(triangle)-2, -1, -1): # 從底到上
for j in range(len(triangle[i])):
dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
return min(dp[0])
問題描述：【Binary Search尝苇、Two Pointers】611. Valid Triangle Number
解題思路：
這道題是給一個數(shù)組铛只，求組成有效三角形的個數(shù)埠胖。
首先這道題肯定是要對數(shù)組排序的。如果采取暴力方法（固定兩條邊淳玩，找第三條邊直撤，時間復(fù)雜度為 O(n^3)，根據(jù)數(shù)據(jù)范圍肯定超時蜕着，pass）谋竖。小于 O(n^3) 的，想著可不可以用 DP 方法做（轉(zhuǎn)移方程不好找承匣，pass）蓖乘。
方法1（Binary Search）：
暴力方法是 O(n^3)，但是由于數(shù)組是排好序的韧骗，我們可以對第三條邊進(jìn)行二分查找嘉抒，找到符合三角形條件的第三條邊最大位置，這樣時間復(fù)雜度為 O(n^2*logn)袍暴。
舉例些侍，nums = [3,4,5,5,6,6,7,8]，固定 3 和 4政模，用二分查找找到第二個 6 的位置（符合三角形條件的第三條邊的最大位置）岗宣，然后累加中間的三角形個數(shù)；固定 3 和 5淋样，用二分查找找到 7 的位置耗式，累加中間的三角形個數(shù)；以此類推趁猴。
Python3 實現(xiàn)：
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
nums.sort()
N = len(nums)
ans = 0
for i in range(N-2):
for j in range(i+1, N-1):
two = nums[i] + nums[j]
k, t = j+1, N-1
while k <= t: # 二分查找第三個數(shù)的最大位置
mid = (k + t) // 2
if two > nums[mid]:
k = mid + 1
else:
t = mid - 1
ans += t - j # 第三個數(shù)的最大位置之前都滿足
return ans
方法2（Two Pointers）：
其實剛開始就在想雙指針的方法刊咳，但是想了一下可能不太行。實際上躲叼，雙指針方法是可以做的芦缰，即對數(shù)組從大到小排序（關(guān)鍵），每次固定最大的數(shù)枫慷，然后使用左右指針找其他兩條邊。如果雙指針指向的兩個數(shù)之和大于第一個數(shù)浪规，說明兩指針之間的情況都滿足（兩條最小的邊大于第三邊）或听。
舉例，nums = [8,7,6,5,4,3,2]（從大到小排序）笋婿，固定 8誉裆，雙指針 low 和 high 分別指向 7 和 2，7 + 2 > 8缸濒，7 和 2 中間都滿足三角形條件足丢，累加 ans粱腻，并執(zhí)行 low += 1；雙指針 low 和 high 分別指向 6 和 2斩跌，6 + 2 <= 8绍些，不滿足三角形條件，執(zhí)行 high -= 1耀鸦；雙指針 low 和 high 分別指向 6 和 3柬批，6 + 3 > 8，6 和 3 中間都滿足三角形條件袖订，累加 ans氮帐，并執(zhí)行 low += 1；以此類推洛姑。
這樣時間復(fù)雜度為 O(n^2)上沐。剛開始沒有想到雙指針的求解思路，是因為思維局限在數(shù)組從小到大排序上了楞艾。
Python3 實現(xiàn)：
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
nums.sort(reverse=True) # 從大到小排序
N = len(nums)
ans = 0
for i in range(N-2):
low, high = i+1, N-1
while low < high:
if nums[low] + nums[high] > nums[i]:
ans += high - low # 雙指針之間都滿足
low += 1
else:
high -= 1
return ans
問題描述：【區(qū)間DP】813. Largest Sum of Averages
解題思路：
這道題是給一個數(shù)組糙俗，將其劃分為 K 個部分，使得每部分平均值加起來最大北滥。
首先想到可以用 DFS 回溯法做井赌，但是看了數(shù)據(jù)范圍，肯定不行舟铜，pass戈盈。然后，能想到的就只有動態(tài)規(guī)劃 DP 了谆刨。
實際上塘娶，這是一道區(qū)間 DP 題目。先定義 DP 數(shù)組痊夭，因為這道題還和 K 有關(guān)刁岸，因此可以定義 dp[N][K]，N 為數(shù)組長度她我，其中 dp[i][j] 表示將前 i 個數(shù)字劃分成前 j 組的最大平均值虹曙。最后，dp[N][K] 就是答案番舆。
接下來的關(guān)鍵酝碳，就是要找狀態(tài)轉(zhuǎn)移方程。將前 i 個數(shù)字劃分成 j 組恨狈，可以對于這 i 個數(shù)字的每個位置 t疏哗，將前 t 個數(shù)字劃分成 j - 1 組，然后將剩下的 i - t 個數(shù)字劃分成第 j 組禾怠。因此返奉，我們可以得到：
dp[i][j] = max(dp[i][j], dp[t][j-1] + (presum[i]-presum[t]) / (i-t)), for each t
其中贝搁，t 是前 i 個數(shù)字的每個位置，presum[i] 表示前 i 個數(shù)字的和芽偏，則 presum[i]-presum[t] 就是剩下的 i - t 個數(shù)字之和雷逆，再除以 i - t 就是剩下的 i - t 個數(shù)字的平均數(shù)。
還有三個要注意的問題：（1）t 的范圍哮针？（2）如何初始化关面？（3）如何遍歷？
- 因為 t 是前 i 個數(shù)字的取值范圍十厢，因此 t 肯定要小于 i（不能等于 i等太，因為 t 要劃分出 j-1 組，最后至少留一個位置 i 來劃分第 j 組）蛮放；又因為
dp[t][j-1]的意義是將前 t 個數(shù)劃分成 j-1 組缩抡，因此t >= j-1（至少要保證 t 個數(shù)足夠多來被 j - 1 劃分）。因此包颁，t 的取值范圍是 [j-1, i)瞻想。 -
當(dāng) K = 1 時，注意到 dp[t][j-1] 是沒有意義的娩嚼，因此要單獨初始化蘑险。K = 1，實際上是將數(shù)組劃分為 1 個部分岳悟，因此轉(zhuǎn)移方程為：
dp[i][1] = presum[i] / i佃迄，即對前 i 個數(shù)直接求平均值即可。 - 首先加上 t贵少，肯定是三層循環(huán)呵俏，而且 t 肯定是最內(nèi)層循環(huán)。但是滔灶，最外層循環(huán)是對 N （或 i）遍歷還是對 K （或 j）進(jìn)行遍歷呢普碎？由問題的實際意義，最外層循環(huán)應(yīng)該是對 K （或 j）進(jìn)行遍歷录平，比如 N = 4麻车，K = 3，如果最外層循環(huán)是 N（或 i）萄涯，那么我們的計算順序是 dp[1][1]绪氛、dp[1][2] ... 很明顯，dp[1][2] 不符合 DP 的定義涝影。如果最外層循環(huán)是 K （或 j），則計算順序是 dp[1][1]争占、dp[2][1]燃逻、dp[3][1]序目、dp[4][1]、dp[2][2] ... 這是符合 DP 定義的伯襟。
考慮到以上問題猿涨，那么問題就可以解決了。時間復(fù)雜度為 O(N*K*N)姆怪，空間復(fù)雜度為 O(N*K)（計算前綴和的空間復(fù)雜度為 O(N)）叛赚。
Python3 實現(xiàn)：
class Solution:
def largestSumOfAverages(self, A: List[int], K: int) -> float:
N = len(A)
presum = [0] * (N+1)
for i in range(1, N+1): # 前綴和, 方便計算平均值
presum[i] = presum[i-1] + A[i-1]
dp = [[0]*(K+1) for _ in range(N+1)]
for i in range(1, N+1): # K為1時單獨初始化，防止下面的dp[t][j-1]沒有意義
dp[i][1] = presum[i] / i
for j in range(2, K+1): # 最外層循環(huán)K, 因為N>=K
for i in range(j, N+1): # 因為i>=j
for t in range(j-1, i): # 因為t>=j-1, 但是t不能比i大
dp[i][j] = max(dp[i][j], dp[t][j-1] + (presum[i]-presum[t])/(i-t))
return dp[-1][-1] # 即dp[N][K]
問題描述：【Array】915. Partition Array into Disjoint Intervals
解題思路：
這道題是給一個數(shù)組稽揭，將其劃分成兩部分俺附，使得左邊所有數(shù)小于等于右邊所有數(shù)，返回劃分位置溪掀。
根據(jù)題意事镣，我們知道左右兩邊數(shù)組滿足左邊的最大值<=右邊的最小值，因此揪胃，我們只需要找到第一處滿足上述條件的位置璃哟，就是最終的答案。
做法：可以使用左右遍歷法喊递，記錄左邊的最大值和右邊的最小值随闪，分別保存在數(shù)組中。然后骚勘，再對原來數(shù)組從左到右遍歷每一個劃分的位置铐伴，去查左最大和右最小數(shù)組，發(fā)現(xiàn)第一個滿足上述條件的位置就是答案调鲸。
這種左右遍歷法是一種典型的犧牲空間換時間的方法盛杰，因此時間復(fù)雜度和空間復(fù)雜度均為 O(n)。
以 A = [5,0,3,8,6] 為例藐石，從左到右遍歷即供，得到左邊最大值數(shù)組為：left = [5,5,5,8,8]；從右到左遍歷于微，得到右邊最小值數(shù)組為：right = [0,0,3,6,6]逗嫡。然后對 A 的每個位置 i，去查 left 和 right 數(shù)組株依，如果發(fā)現(xiàn) left[i] <= right[i+1]驱证，即左邊的最大值<=右邊的最小值，滿足題意恋腕，位置 i+1 就是答案抹锄。
Python3 實現(xiàn)：
class Solution:
def partitionDisjoint(self, A: List[int]) -> int:
N = len(A)
left_max, right_min = [A[0]] * N, [A[-1]] * N
for i in range(1, N): # 左邊最大值數(shù)組，從左到右遍歷
left_max[i] = max(left_max[i-1], A[i])
for i in range(N-2, -1, -1): # 右邊最小值數(shù)組，從右到左遍歷
right_min[i] = min(right_min[i+1], A[i])
for i in range(N-1):
if left_max[i] <= right_min[i+1]: # 存在一種劃分
return i+1
改進(jìn)：左邊最大值可以在最后從左到右遍歷的過程中更新伙单，因此沒必要計算左邊最大值數(shù)組获高，用一個變量即可。改進(jìn)后的代碼如下：
class Solution:
def partitionDisjoint(self, A: List[int]) -> int:
N = len(A)
left_max = float("-inf") # 用一個變量記錄左邊最大值
right_min = [A[-1]] * N
for i in range(N-2, -1, -1): # 右邊最小值數(shù)組
right_min[i] = min(right_min[i+1], A[i])
for i in range(N-1):
left_max = max(left_max, A[i]) # 更新左邊最大值
if left_max <= right_min[i+1]: # 存在一種劃分
return i+1
