【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] * 3
        if nums[0] == nums[1]:
            dp[1] = True
        if (nums[0] == nums[1] and nums[0] == nums[2]) or (nums[1] + 1 == nums[2] and nums[0] + 2 == nums[2]):
            dp[2] = True
        for 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], r
        return 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] = True
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    if j - i == 1:
                        dp_huiwen[i][j] = True
                    else:
                        dp_huiwen[i][j] = dp_huiwen[i + 1][j - 1]

        dp = [n] * n
        dp[0] = 0
        for i in range(1, n):
            for j in range(i + 1):
                if dp_huiwen[j][i]:
                    if j == 0:
                        dp[i] = 0
                    else:
                        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] * n
        for 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] = True
            for 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 True
        return 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 = 0
        right = end
        while left <= right:
            mid = left + (right - left) // 2
            if sorted_combined[mid][1] > start_time:
                right = mid - 1
            else:
                left = mid + 1
        return right

原文地址：https://blog.csdn.net/zs16113/article/details/143418808

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！