Lemmy - 6 months ago 9x
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.

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