I have a solution to a problem that uses dynamic programming. I need help turning this from a recursive solution into an iterative one.

The function takes in a number and follows the three rules:

1. it may divide the number in half
2. it may subtract one
3. it may add one

until the number is 1. My goal is to find the minimum number of steps it takes to do this.

Here is my solution:

def solution(n):
    n = int(n)
    memo = {}
    return memoized_fuel_injection_perfection(n, memo)
        
def memoized_fuel_injection_perfection(n, memo):
    if n == 1:
        return 0
    if n == 2:
        return 1
    if n in memo:
        return memo[n]
    if n % 2 == 0:
        if n not in memo:
            memo[n] = memoized_fuel_injection_perfection(n//2, memo)   1
        return memo[n]
    return min(memoized_fuel_injection_perfection(n-1, memo), memoized_fuel_injection_perfection(n 1, memo))   1

But when I input numbers larger than 300 digits long, I am getting a recursive error. How can I turn this into an iterative solution? Any help or guidance is appreciated.

Here is an iterative solution I created, but I am getting MemoryError with very large inputs. Is there some way I can optimize storing the variables so I don't have to compute them for every number?

def solution(n):
    memo = {}
    memo[0] = 0
    memo[1] = 0
    memo[2] = 1
    n = int(n)
    for i in range(3, n 1):
        if i % 2 == 0:
            memo[i] = memo[i//2]   1
        else:
            memo[i] = min(memo[i//2], memo[i//2   1])   2
    
    return memo[n]

CodePudding user response：

The problem you said you're having with writing an iterative solution is the use of memoized_fuel_injection_perfection(n 1, memo), which makes it tricky to determine what order to compute results in. The key is that you cannot repeatedly go down this code path indefinitely. If you could, even your recursive solution would be invalid.

Immediately after a 1 or -1 operation, you always perform a divide-by-2. We can fuse the 1 or -1 with the divide-by-2, producing an operation that cannot increase the number. The core of an iterative solution would then look like this:

if n % 2 == 0:
    table[n] = table[n//2]   1
else:
    table[n] = min(table[n//2], table[n//2 1])   2

Can you complete things from there? (You'll need a way to avoid computing results for every positive integer less than n.)

CodePudding user response：

Here's my attempt:

def solution(n):
    def is_even(n): # helper function
        return n % 2 == 0

    possible_nodes = {1} # 1 is the destination
    consider = [n] # stack: numbers to be considered
    while consider: # as long as non-empty
        x = consider.pop() # now think about where can we move from x
        if x in possible_nodes: # if it is already handled before
            continue
        if is_even(x): # if even, we just halve it
            consider.append(x//2)
        else: # otherwise, -1 or  1
            consider  = [x-1, x 1]
        possible_nodes.add(x) # mark x as 'considered'

    steps = {1: 0} # dict to store min steps

    for x in filter(is_even, sorted(possible_nodes)): # odds calculated only when needed
        if x//2 not in steps: # if x//2 was not computed, x//2 must be odd
            steps[x//2] = min(steps[x//2 - 1], steps[x//2   1])   1
        steps[x] = steps[x//2]   1

    return steps[n] if is_even(n) or n == 1 else min(steps[n-1], steps[n 1])   1

n = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003333000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003483983333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
print(solution(n)) # 2467

print(*(solution(i) for i in range(1, 21)))
# 0 1 2 2 3 3 4 3 4 4 5 4 5 5 5 4 5 5 6 5

The code basically consists of two steps. In the first step, it enumerates all the possible steps from n, under the rule that for x,

1. if x is even, we only consider x//2 as the next step; this strategy is adopted also in your code;
2. if x is odd, we consider x-1 and x 1 as the next step.

I did this because calculating the minimum steps for all values up to n is wasteful. (Actually at first I tried to do so by initiating something like [None] * n, but it seems like python cannot handle such a long list. Even if it can, I guess that would be extremely slow.)

The next step is calculating the minimum steps, starting from the smallest number. I address the problem of accessingsteps[x 1] by "not calculating steps[x] for odd x eagerly." We only calculate steps[x] for even x eagerly, but lazily for odd x.

The rationale is the following; by the time odd x is needed, it must be the case that x is either k//2 - 1 or k//2 1 for some even k, which must be larger than x 1. Since x 1 is even, step[x 1] must have been already calculated, by the construction of the for loop.