Daniel Chepenko - 5 months ago 680

Python Question

I'm dealing with the problem, that is pretty similar to change coins problem.

I need to implement a simple calculator, that can perform the following three operations with the current number x: multiply x by 2, multiply x by 3, or add 1 to x.

Goal is given a positive integer n, find the minimum number of operations needed to obtain the number n starting from the number 1.

I made a greedy approach to that, bur it shows incorrect results

`import sys`

def optimal_sequence(n):

sequence = []

while n >= 1:

sequence.append(n)

if n % 3 == 0:

n = n // 3

elif n % 2 == 0:

n = n // 2

else:

n = n - 1

return reversed(sequence)

input = sys.stdin.read()

n = int(input)

sequence = list(optimal_sequence(n))

print(len(sequence) - 1)

for x in sequence:

print(x)

For example:

`Input: 10`

Output:

4

1 2 4 5 10

4 steps. But the correct one is 3 steps:

`Output:`

3

1 3 9 10

I read about dynamic programming, and hope I could implement it here. But, I can't get how to use it properly in particular case, can someone give me an advice?

Answer

Just solve it with a simple recursion and Memoization:

Code:

```
d = {}
def f(n):
if n == 1:
return 1, -1
if d.get(n) is not None:
return d[n]
ans = (f(n - 1)[0] + 1, n - 1)
if n % 2 == 0:
ret = f(n // 2)
if ans[0] > ret[0]:
ans = (ret[0] + 1, n // 2)
if n % 3 == 0:
ret = f(n // 3)
if ans[0] > ret[0]:
ans = (ret[0] + 1, n // 3)
d[n] = ans
return ans
def print_solution(n):
if f(n)[1] != -1:
print_solution(f(n)[1])
print n,
def solve(n):
print f(n)[0]
print_solution(n)
print ''
solve(10)
```

Hint: f(x) returns a tuple (a, b), which `a`

denotes the minimum steps to get x from 1, and `b`

denotes the previous number to get the optimum solution. `b`

is only used for print the solution.

Output:

```
4 # solution for 10
1 3 9 10
7 # solution for 111
1 2 4 12 36 37 111
```

You may debug my code and to learn how it works. If you are beginner at DP, you could read my another SO post about DP to get a quick start.

Source (Stackoverflow)

Comments