Skip to content

DP Optimal Partitioning

Table of Contents

132. Palindrome Partitioning II

132. Palindrome Partitioning II - Python Solution
from functools import cache


# Memoization
def minCutMemoization(s: str) -> int:
    @cache
    def is_palindrome(left, right):
        if left >= right:
            return True
        return s[left] == s[right] and is_palindrome(left + 1, right - 1)

    @cache
    def dfs(right):
        if is_palindrome(0, right):
            return 0
        res = float("inf")
        for left in range(1, right + 1):
            if is_palindrome(left, right):
                res = min(res, 1 + dfs(left - 1))
        return res

    return dfs(len(s) - 1)


# Tabulation
def minCutTabulation(s: str) -> int:
    n = len(s)
    is_palindrome = [[True] * n for _ in range(n)]

    for left in range(n - 2, -1, -1):
        for right in range(left + 1, n):
            is_palindrome[left][right] = (
                s[left] == s[right] and is_palindrome[left + 1][right - 1]
            )

    dp = [0 for _ in range(n)]

    for right, is_pal in enumerate(is_palindrome[0]):
        if is_pal:
            continue
        res = float("inf")
        for left in range(1, right + 1):
            if is_palindrome[left][right]:
                res = min(res, 1 + dp[left - 1])
        dp[right] = res

    return dp[-1]


s = "aab"
print(minCutMemoization(s))  # 1
print(minCutTabulation(s))  # 1

2707. Extra Characters in a String

3196. Maximize Total Cost of Alternating Subarrays

2767. Partition String Into Minimum Beautiful Substrings

91. Decode Ways

91. Decode Ways - Python Solution
# DP
def numDecodingsDP(s: str) -> int:
    if not s or s[0] == "0":
        return 0

    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(1, n + 1):
        # Check single digit decode
        if s[i - 1] != "0":
            dp[i] += dp[i - 1]

        # Check two digit decode
        if i > 1 and "10" <= s[i - 2 : i] <= "26":
            dp[i] += dp[i - 2]

    return dp[n]


# DFS
def numDecodingsDFS(s: str) -> int:
    memo = {}

    def dfs(i):
        if i == len(s):
            return 1

        if s[i] == "0":
            return 0

        if i in memo:
            return memo[i]

        # Single digit decode
        ways = dfs(i + 1)

        # Two digits decode
        if i + 1 < len(s) and "10" <= s[i : i + 2] <= "26":
            ways += dfs(i + 2)

        memo[i] = ways

        return ways

    return dfs(0)


s = "226"
print(numDecodingsDP(s))  # 3
print(numDecodingsDFS(s))  # 3

639. Decode Ways II

1043. Partition Array for Maximum Sum

1416. Restore The Array

2472. Maximum Number of Non-overlapping Palindrome Substrings

1105. Filling Bookcase Shelves

2547. Minimum Cost to Split an Array

2430. Maximum Deletions on a String

  • LeetCode | LeetCode CH (Hard)

  • Tags: string, dynamic programming, rolling hash, string matching, hash function

2463. Minimum Total Distance Traveled

2977. Minimum Cost to Convert String II

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, string, dynamic programming, graph, trie, shortest path

3441. Minimum Cost Good Caption

2052. Minimum Cost to Separate Sentence Into Rows

2464. Minimum Subarrays in a Valid Split

Comments