Leetcode【120、611、813、915】
Leetcode【120、611、813、915】
问题描述：【DP】120. Triangle
解题思路：
这道题是给一个三角形，从顶到下计算最小路径和。
容易想到用动态规划求解，dp[i][j] 存储累加到位置 (i, j) 的最小路径和。
如果是从顶到下，那么转移方程为 dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]，但是会发现，对于第 i 行的在最后一个数字 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]，不会出现越界情况，最后 dp[0] 就是答案。采取从底向上方法时，注意先初始化最后一行。
Python3 实现：
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
解题思路：
这道题是给一个数组，求组成有效三角形的个数。
首先这道题肯定是要对数组排序的。如果采取暴力方法（固定两条边，找第三条边，时间复杂度为 O(n^3)，根据数据范围肯定超时，pass）。小于 O(n^3) 的，想着可不可以用 DP 方法做（转移方程不好找，pass）。
方法1（Binary Search）：
暴力方法是 O(n^3)，但是由于数组是排好序的，我们可以对第三条边进行二分查找，找到符合三角形条件的第三条边最大位置，这样时间复杂度为 O(n^2*logn)。
举例，nums = [3,4,5,5,6,6,7,8]，固定 3 和 4，用二分查找找到第二个 6 的位置（符合三角形条件的第三条边的最大位置），然后累加中间的三角形个数；固定 3 和 5，用二分查找找到 7 的位置，累加中间的三角形个数；以此类推。
Python3 实现：
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: # 二分查找第三个数的最大位置
mid = (k + t) // 2
if two > nums[mid]:
k = mid + 1
else:
t = mid - 1
ans += t - j # 第三个数的最大位置之前都满足
return ans方法2（Two Pointers）：
其实刚开始就在想双指针的方法，但是想了一下可能不太行。实际上，双指针方法是可以做的，即对数组从大到小排序（关键），每次固定最大的数，然后使用左右指针找其他两条边。如果双指针指向的两个数之和大于第一个数，说明两指针之间的情况都满足（两条最小的边大于第三边）。
举例，nums = [8,7,6,5,4,3,2]（从大到小排序），固定 8，双指针 low 和 high 分别指向 7 和 2，7 + 2 > 8，7 和 2 中间都满足三角形条件，累加 ans，并执行 low += 1；双指针 low 和 high 分别指向 6 和 2，6 + 2 <= 8，不满足三角形条件，执行 high -= 1；双指针 low 和 high 分别指向 6 和 3，6 + 3 > 8，6 和 3 中间都满足三角形条件，累加 ans，并执行 low += 1；以此类推。
这样时间复杂度为 O(n^2)。刚开始没有想到双指针的求解思路，是因为思维局限在数组从小到大排序上了。
Python3 实现：
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问题描述：【区间DP】813. Largest Sum of Averages
解题思路：
这道题是给一个数组，将其划分为 K 个部分，使得每部分平均值加起来最大。
首先想到可以用 DFS 回溯法做，但是看了数据范围，肯定不行，pass。然后，能想到的就只有动态规划 DP 了。
实际上，这是一道区间 DP 题目。先定义 DP 数组，因为这道题还和 K 有关，因此可以定义 dp[N][K]，N 为数组长度，其中 dp[i][j] 表示将前 i 个数字划分成前 j 组的最大平均值。最后，dp[N][K] 就是答案。
接下来的关键，就是要找状态转移方程。将前 i 个数字划分成 j 组，可以对于这 i 个数字的每个位置 t，将前 t 个数字划分成 j - 1 组，然后将剩下的 i - t 个数字划分成第 j 组。因此，我们可以得到：
dp[i][j] = max(dp[i][j], dp[t][j-1] + (presum[i]-presum[t]) / (i-t)), for each t
其中，t 是前 i 个数字的每个位置，presum[i] 表示前 i 个数字的和，则 presum[i]-presum[t] 就是剩下的 i - t 个数字之和，再除以 i - t 就是剩下的 i - t 个数字的平均数。
还有三个要注意的问题：（1）t 的范围？（2）如何初始化？（3）如何遍历？
- 因为 t 是前 i 个数字的取值范围，因此 t 肯定要小于 i（不能等于 i，因为 t 要划分出 j-1 组，最后至少留一个位置 i 来划分第 j 组）；又因为
dp[t][j-1]的意义是将前 t 个数划分成 j-1 组，因此t >= j-1（至少要保证 t 个数足够多来被 j - 1 划分）。因此，t 的取值范围是 [j-1, i)。 - 当 K = 1 时，注意到 dp[t][j-1] 是没有意义的，因此要单独初始化。K = 1，实际上是将数组划分为 1 个部分，因此转移方程为：
dp[i][1] = presum[i] / i，即对前 i 个数直接求平均值即可。 - 首先加上 t，肯定是三层循环，而且 t 肯定是最内层循环。但是，最外层循环是对 N （或 i）遍历还是对 K （或 j）进行遍历呢？由问题的实际意义，最外层循环应该是对 K （或 j）进行遍历，比如 N = 4，K = 3，如果最外层循环是 N（或 i），那么我们的计算顺序是 dp[1][1]、dp[1][2] ... 很明显，dp[1][2] 不符合 DP 的定义。如果最外层循环是 K （或 j），则计算顺序是 dp[1][1]、dp[2][1]、dp[3][1]、dp[4][1]、dp[2][2] ... 这是符合 DP 定义的。
考虑到以上问题，那么问题就可以解决了。时间复杂度为 O(N*K*N)，空间复杂度为 O(N*K)（计算前缀和的空间复杂度为 O(N)）。
Python3 实现：
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): # 最外层循环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
解题思路：
这道题是给一个数组，将其划分成两部分，使得左边所有数小于等于右边所有数，返回划分位置。
根据题意，我们知道左右两边数组满足左边的最大值<=右边的最小值，因此，我们只需要找到第一处满足上述条件的位置，就是最终的答案。
做法：可以使用左右遍历法，记录左边的最大值和右边的最小值，分别保存在数组中。然后，再对原来数组从左到右遍历每一个划分的位置，去查左最大和右最小数组，发现第一个满足上述条件的位置就是答案。
这种左右遍历法是一种典型的牺牲空间换时间的方法，因此时间复杂度和空间复杂度均为 O(n)。
以 A = [5,0,3,8,6] 为例，从左到右遍历，得到左边最大值数组为：left = [5,5,5,8,8]；从右到左遍历，得到右边最小值数组为：right = [0,0,3,6,6]。然后对 A 的每个位置 i，去查 left 和 right 数组，如果发现 left[i] <= right[i+1]，即左边的最大值<=右边的最小值，满足题意，位置 i+1 就是答案。
Python3 实现：
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): # 左边最大值数组，从左到右遍历
left_max[i] = max(left_max[i-1], A[i])
for i in range(N-2, -1, -1): # 右边最小值数组，从右到左遍历
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改进：左边最大值可以在最后从左到右遍历的过程中更新，因此没必要计算左边最大值数组，用一个变量即可。改进后的代码如下：
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): # 右边最小值数组
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腾讯云开发者
