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 = 
for i in range(2,n+1):
op.append(1) # INCORRECT
opt[i] = min(1+opt[i/2],opt[i])
op[-1]=2 # INCORRECT
opt[i] = min(1+opt[i/3],opt[i])
op[-1]=3 # INCORRECT
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)
(3, [1, 3, 3])
Meaning: 3 operations, which are
See it run on eval.in