Problem statement

https://leetcode.com/problems/how-many-apples-can-you-put-into-the-basket/

Solution

This problem is similar to problems 0664. Strange Printer, 0546 Remove Boxes and to 0312 Burst Balloons. All this problem have similarity that when we remove some adjacent elemens, elements from the left and right are merged. Imagine the following example for more visualization:

xycabadcyxijklkommji and do the following steps:

xycabadcyxijklkommji -> xycdcyxijklkommji -> xycdcyxijklkoji -> xycdcyxijoji -> xycdcyx -> xyx -> ""

Let us look in original string, what intervals we processed:

x y c a b a d c y x i j k l k o m m j i

. . . _ _ _ . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . _ _ . .

. . . . . . . . . . . . _ _ _ . . . . .

. . . . . . . . . . _ _ _ _ _ _ _ _ _ _

. . _ _ _ _ _ _ . . . . . . . . . . . .

_ _ _ _ _ _ _ _ _ _ . . . . . . . . . .

Then these intervals have property: either they do not intersect or one lies fully in another. Also there will be interval which have the most left element and in this case we can say that problem is separated into two subproblems, which do not intersect, call this interval nice. There can be different ways to choose this nice inteval, but it always exist. Also for this element holds, that arr[i] = arr[k], that is its start and end must be equal. So, algorithm can be written as follow:

Let dp(i, j) be answer for interval [i, j]. There can be 3 cases how to choose nice inteval:

  1. It has only one element, for this case we need to consider dp(i+1, j).
  2. It has all elements, in this case arr[i] == arr[j] holds and we can cut the first and the last elements and look at the solution for dp(i+1, j-1).
  3. It is somewhere in the middle, then we need to have property arr[i] == arr[k] and we need to consider dp(i, k) + dp(k+1, j), because we have two subproblems which do not intersect.

Complexity

We have O(n^2) states with O(n) transactions from one state to another, sot total time complexity is O(n^3). Space complexity is O(n^2). Note, that time complexity can be optimized a bit, if we keep indexes for each value: then instead of traversing all indexes from i + 1 to j we can check only indexes with value arr[i].

Code

class Solution:
    def minimumMoves(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
        
        return dp(0, len(arr)-1)

Remark

I wonder if it is possible to apply the same proof to the similar problem I provided, TBD