How can I convert this recursive function into a dynamic algorithm?

user_17195523 0
Viewed 60

I am currently working on this problem:

A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10, then making the first cut at position 3 incurs a total cost of 20+17=37, while doing position 10 first has a better cost of 20+10=30. Give a dynamic programming algorithm that, given the locations of m cuts in a string of length n, finds the minimum cost of breaking the string into m + 1 pieces.

I managed to represent the problem as a recurrence and came up with the following recursive solution to the problem.

def recursive(M, N):
if len(M) == 0:
    return 0
else:
    c_min = float('inf')
    for c in M:
        lt_cuts = [d for d in M if d < c]
        gt_cuts = [e - c for e in M if e > c]
        c_min = min(c_min, N + recursive(lt_cuts, c) + recursive(gt_cuts, N - c))

return c_min

Normally once I find the recursive form of a problem, adapting it to a dynamic algorithm is pretty easy. This time I've been banging my head against this problem for an entire day and I can't find a single working solution. Can anyone give me some hints or useful snippets? Anything would be appreciated.

dynamic-programming recursion substring algorithm python
1 Answers

Lets number the cuts from 1 to m, and we'll call the start of the string "cut 0" and the end of the string "cut m+1".

Now, each call to your recursive function calculates a cost(i,j), which is the minimum cost to cut up the part of the string between cut i and cut j, with i < j.

In the calculation of cost(i,j), you will only make recursive calls for smaller regions. If you call cost(a,b), then you will have (b-a) < (j-i).

Therefore, you can make a dynamic programming implementation by creating a matrix COST, where COST[i][j] = cost(i,j). If you fill the matrix in order of increasing region length (j-i), then you are guaranteed that all the entries that you need to calculate any COST[i][j] will be done by the time you need them.

For example, given all the cut positions (including the start and end) in cuts:

# costs for all length-1 regions
for i in range(len(cuts)):
    COST[i][i+1] = 0

# costs for other sizes
for size in range(2,len(cuts)+1):
    for i in range(len(cuts)-size+1):
        j = i+size

        # cost for this region if we start by cutting at i+1
        subcost = COST[i][i+1] + COST[i+1,j]

        # costs for other initial cuts
        for cut in range(i+2,j):
            subcost = min(subcost, COST[i][cut] + COST[cut,j])

        # add the cost of the initial cut
        COST[i][j] = subcost + cuts[j] - cuts[i]
user_54835260
Related