Primitive Calculator

We always start from 1, and we get the positive integer we should get to. We could apply just three operations, multiply by 2, by 3, or adding one. Which is the minimum number of operations that gives us the expected result? Which sequence will be generated?

This problem is close to the previous one, about changing money. After all, are all part of the same lot about Dynamic Programming.

The first part of the code follows almost naturally from looking at the money changer:

cache = [0] * (target + 1)  # 1
for i in range(1, len(cache)):  # 2
    cache[i] = cache[i-1] + 1
    if i % 2 == 0:
        cache[i] = min(cache[i], cache[i // 2] + 1)
    if i % 3 == 0:
        cache[i] = min(cache[i], cache[i // 3] + 1)

1. Reserve a cache for all the intermediate results, again, a dummy zeroth element would make our code simpler.
2. Loop an all the elements, checking for all the possible alternatives. The minimum local solution would be kept an used to the next steps.

Now in the last element of the cache we have the answer to the first question. To get the second answer we need to backtrack the cache, identify each choice we did at each step.

result = [1] * cache[-1]  # 1
for i in range(1, cache[-1]):  # 2
    result[-i] = target  # 3
    if cache[target-1] == cache[target] - 1:  # 4
        target -= 1
    elif target % 2 == 0 and (cache[target // 2] == cache[target] - 1):  # 5
        target //= 2
    else:  # 6 # target % 3 == 0 and (cache[target // 3] == cache[target] - 1):
        target //= 3
return result

1. This is the list we are going to return. We know its size, stored in the last element of the cache, since I have to provide an initialization value, I use 1, the right value for its leftmost element.
2. I am going to set the result list, each value but the leftmost one, already correctly set.
3. I know the rightmost value would be the target passed by the user.
4. If the previous element in the cache is the current value of the cache minus one, I got there adding one, so I here apply the inverse operator, decreasing target by one
5. If the current target is divisible by 2, and the cache at position current divided by two is actually the value of the current element of the cache minus one, we got there multiplying by two. So I apply the inverse to backtrace.
6. Otherwise we got there multiplying by three. I could have written the full elif statement as shown in the comment. The point is that by construction we have only three choices to get to an element in the cache and this must be the third one.

Python code and testcase on GitHub.