BinarySearch 0707 Removing Palindromic Sublists

Problem statement

https://binarysearch.com/problems/Removing-Palindromic-Sublists/

Solution

Equal to Leetcode 1246 Palindrome Removal.

Complexity

It is O(n^3) for time and O(n^2) for space.

Code

class Solution:
    def solve(self, arr):
        @lru_cache(None)
        def dp(i, j):
            if i >= j: return 1
            res = 1 + dp(i+1, j)
            if arr[i] == arr[j]: res = min(res, dp(i+1, j-1))
            for k in range(i + 1, j):
                if arr[i] == arr[k]:
                    res = min(res, dp(i, k) + dp(k+1, j))
            return res
        
        if not arr: return 0
        return dp(0, len(arr)-1)