【leetcode】动态规划刷题总结-划分问题

判定能否划分

一般定义dp[i]表示nums[:i + 1]能否划分，然后枚举最后一个子数组的左端点，得到nums[:i + 1]能否划分

LeetCode2369题 检查数组是否存在有效划分

class Solution:def validPartition(self, nums: List[int]) -> bool:if len(nums) == 2:return nums[0] == nums[1]# dp[i]表示nums[:i + 1]是否存在有效划分# dp[i] = (nums[i - 1] == nums[i] and dp[i - 2]) or \#         (nums[i - 1] == nums[i] and nums[i - 2] == nums[i] and dp[i - 3]) or \#         (nums[i - 1] + 1 == nums[i] and nums[i - 2] + 2 == nums[i] and dp[i - 3])dp = [False] * 3if nums[0] == nums[1]:dp[1] = Trueif (nums[0] == nums[1] and nums[0] == nums[2]) or (nums[1] + 1 == nums[2] and nums[0] + 2 == nums[2]):dp[2] = Truefor i in range(3, len(nums)):r = (nums[i - 1] == nums[i] and dp[- 2]) or \(nums[i - 1] == nums[i] and nums[i - 2] == nums[i] and dp[- 3]) or \(nums[i - 1] + 1 == nums[i] and nums[i - 2] + 2 == nums[i] and dp[- 3])dp[0], dp[1], dp[2] = dp[1], dp[2], rreturn dp[-1]

最优划分

一般定义dp[i]表示nums[:i + 1]分割出满足条件的最少（最多）划分方案数，然后枚举最后一个子数组的左端点，计算nums[:i + 1]最优划分

LeetCode132题 分割回文串II

先使用区间DP解法记录s[i:j + 1]是否是回文子串，然后再用划分DP解法

class Solution:def minCut(self, s: str) -> int:# dp[i]表示s[:i + 1]分割为一些回文串的最少分割次数# dp[i] = min(dp[i], dp[j - 1] + 1) 0 <= j <= i# dp_huiwen[i][j]表示s[i: j + 1]是否是回文子串# dp_huiwen[i][j] = s[i] == s[j] and dp_huiwen[i + 1][j - 1]n = len(s)dp_huiwen = [[False] * n for _ in range(n)]for i in range(n - 1, -1, -1):dp_huiwen[i][i] = Truefor j in range(i + 1, n):if s[i] == s[j]:if j - i == 1:dp_huiwen[i][j] = Trueelse:dp_huiwen[i][j] = dp_huiwen[i + 1][j - 1]dp = [n] * ndp[0] = 0for i in range(1, n):for j in range(i + 1):if dp_huiwen[j][i]:if j == 0:dp[i] = 0else:dp[i] = min(dp[i], dp[j - 1] + 1)return dp[-1]

约束划分个数

将数组划分为（恰好/至多）k个子数组，计算与这些子数组有关的最优值。一般定义dp[i][j]表示将nums[:j + 1]划分为i个子数组所得到的最优解

LeetCode1043题 分隔数组以得到最大值

class Solution:def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:# dp[i]表示分隔arr[:i + 1]得到的最大和# dp[i] = max{dp[j - 1] + max(arr[j: i + 1]) * (i - j + 1) | i - k + 1 <= j <= i}n = len(arr)dp = [0] * nfor i in range(n):max_val = arr[i]# j代表与arr[i]一组的左侧索引# 倒序遍历为了方便求最大值for j in range(i, max(i - k, -1), -1):max_val = max(max_val, arr[j])if j == 0:dp[i] = max(dp[i], max_val * (i - j + 1))else:dp[i] = max(dp[i], dp[j - 1] + max_val * (i - j + 1))return dp[-1]

LeetCode1745题 分割回文串IV

class Solution:def checkPartitioning(self, s: str) -> bool:# dp[i][j]表示s[i:j + 1]是否是回文串# dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]n = len(s)dp = [[False] * n for _ in range(n)]for i in range(n - 1, -1, -1):dp[i][i] = Truefor j in range(i + 1, n):if j - i == 1:dp[i][j] = s[i] == s[j]else:dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]# i代表第2个回文子串开头索引，j代表第3个回文子串开头索引for i in range(1, n - 1):for j in range(i + 1, n):if dp[0][i - 1] and dp[i][j - 1] and dp[j][n - 1]:return Truereturn False

 LeetCode813题 最大平均值和的分组

class Solution:def largestSumOfAverages(self, nums: List[int], k: int) -> float:# dp[i][j]表示nums[:i + 1]分成最多j个非空子数组的最大平均值和# dp[i][j] = max{ dp[s - 1][j - 1] + sum(nums[s:i + 1]) / (i - s + 1) | 0 <= s <= i}# 其中s表示和nums[i]一组的左侧元素索引n = len(nums)prefix_nums = [nums[0]]for i in range(1, n):prefix_nums.append(prefix_nums[-1] + nums[i])dp = [[0] * (k) for _ in range(n)]for i in range(n):dp[i][0] = prefix_nums[i] / (i + 1)for j in range(1, k):for s in range(0, i + 1):if s == 0:dp[i][j] = max(dp[i][j], prefix_nums[i] / (i - s + 1))else:dp[i][j] = max(dp[i][j], dp[s - 1][j - 1] + (prefix_nums[i] - prefix_nums[s - 1]) / (i - s + 1))return dp[-1][-1]

LeetCode1235题 规划兼职工作

先按照结束时间排序，然后分类讨论，求出按照结束时间排序后的前i个工作的最大报酬：

• 不选第 i 个工作，那么最大报酬等于前i−1个工作的最大报酬（转换成了一个规模更小的子问题）
• 选第 i 个工作，由于工作时间不能重叠，设k是最大的满足endTime[k]≤startTime[i]的k，那么最大报酬等于前k个工作的最大报酬加上profit[i]（同样转换成了一个规模更小的子问题）

这两种决策取最大值。其中第二个情况可以用二分查找得到动态规划递推公式的信息，复杂度O(n*logn)

class Solution:def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:sorted_combined = sorted(zip(startTime, endTime, profit), key=lambda x: (x[1], x[0]))# dp[i]表示0-i的工作的最大报酬# dp[i] = max(dp[i - 1], dp[k] + profit[i])dp = [0] * len(sorted_combined)dp[0] = sorted_combined[0][2]for i in range(1, len(sorted_combined)):k = self.search(sorted_combined, i - 1, sorted_combined[i][0])dp[i] = max(dp[i - 1], dp[k] + sorted_combined[i][2])return dp[-1]def search(self, sorted_combined, end, start_time):# endTime中寻找小于等于start_time的右边界left = 0right = endwhile left <= right:mid = left + (right - left) // 2if sorted_combined[mid][1] > start_time:right = mid - 1else:left = mid + 1return right