Skip to content

DP Constrained Number of Partitions

Table of Contents

410. Split Array Largest Sum

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, dynamic programming, greedy, prefix sum

813. Largest Sum of Averages

1278. Palindrome Partitioning III

1278. Palindrome Partitioning III - Python Solution
# DP
def palindromePartition(s: str, k: int) -> int:
    n = len(s)
    min_change = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            min_change[i][j] = min_change[i + 1][j - 1] + (
                1 if s[i] != s[j] else 0
            )

    dp = min_change[0]
    for i in range(1, k):
        for right in range(n - k + i, i - 1, -1):
            dp[right] = min(
                dp[left - 1] + min_change[left][right]
                for left in range(i, right + 1)
            )

    return dp[-1]


s = "aabbc"
k = 3
print(palindromePartition(s, k))  # 0

1745. Palindrome Partitioning IV

1745. Palindrome Partitioning IV - Python Solution
# DP
def checkPartitioning(s: str) -> bool:
    def palidrome_partition(s, k):
        n = len(s)
        min_change = [[0] * n for _ in range(n)]
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                min_change[i][j] = min_change[i + 1][j - 1] + (
                    1 if s[i] != s[j] else 0
                )

        dp = min_change[0]

        for i in range(1, k):
            for right in range(n - k + i, i - 1, -1):
                dp[right] = min(
                    dp[left - 1] + min_change[left][right]
                    for left in range(i, right + 1)
                )

        return dp[-1]

    return palidrome_partition(s, 3) == 0


s = "abcbdd"
print(checkPartitioning(s))  # True

1335. Minimum Difficulty of a Job Schedule

1473. Paint House III

2209. Minimum White Tiles After Covering With Carpets

1478. Allocate Mailboxes

1959. Minimum Total Space Wasted With K Resizing Operations

2478. Number of Beautiful Partitions

3077. Maximum Strength of K Disjoint Subarrays

2911. Minimum Changes to Make K Semi-palindromes

3117. Minimum Sum of Values by Dividing Array

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, dynamic programming, bit manipulation, segment tree, queue

Comments