Lemmy Lemmy - 1 year ago 53
Python Question

How to get set of operations in dynamic programming

I would like to ask you how can I get a list of operations I have to do to obtain the result.

The simple example:

There is a number N. Your goal is to find out the minimum operations (x/3, x/2, x-1) you have to do to get 1.

So for example minop(10) = 3 (because 1. 10-1=9, 2. 9/3=3, 3. 3/3=1).

This function is very simple with bottom-up approach in Python:

# the opt is an optimum nuber of operations for index to get to one
# the op list should be a list of operations but it does not work
# correctly. For minop(10) would return opt = 3 (three
#operations), op = [1,3,3] (minus one, divide three, divide three)

opt = [0,0,0,0,0,0,0,0,0,0,0,0] # optimum number of operation for i
op = []

def minop(n):
for i in range(2,n+1):
op.append(1) # INCORRECT
if i%2==0:
opt[i] = min(1+opt[i/2],opt[i])
op[-1]=2 # INCORRECT
if i%3==0:
opt[i] = min(1+opt[i/3],opt[i])
op[-1]=3 # INCORRECT
return opt[n],op

As you can see, the op list should contain minimum list of operations (represented by numbers) needed to get from
but it contains.

Answer Source

The most important error in your code is that you update opt[i] in both if blocks even if the operation does not yield a better result.

Here is a corrected version of your code:

def minop(n):
    op = [[], []]
    for i in range(2,n+1):
        ref = i-1
        best = 1
        if i%2==0 and len(op[i/2]) < len(op[ref]):
            ref = i/2
            best = 2
        if i%3==0 and len(op[i/3]) < len(op[ref]):
            ref = i/3
            best = 3
        op.append([best] + op[ref][:]) # slice to get separate copy
    return len(op[n]), op[n]

print minop(10)

It outputs:

(3, [1, 3, 3])

Meaning: 3 operations, which are -1, /3, /3.

See it run on eval.in