Lemmy Lemmy - 7 months ago 21
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):
opt[1]=0
for i in range(2,n+1):
opt[i]=opt[i-1]+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
n
to
1
but it contains.

Answer

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