Минимальные шаги к одному Python

Question

Я пробовал этот код, но он не работает, и результаты с 0. Я знаю рекурсивный, но я пытаюсь сделать это, используя для цикла.

def minsteps(n): 
    memo =[0]*(n+1) 
    memo[0] = 0 
    memo[1] = 0 
    for i in range(2,n,1): 
     r = 1+memo[i-1] 
     if i%2 == 0: 
      r = min(r, 1+memo[i//2]) 
     elif i%3 == 0: 
      r = min(r, 1+memo[i//3]) 
     memo[i] = r 
    return memo[n] 

Этот код, чтобы обеспечить минимальные шаги необходимо для определенного количества, чтобы быть 1, подвергающиеся процессы минус 1, 2 делят и делят 3. Например: 6-> 2-> 1 [3] или 6-> 3-> 1 [3] или 6-> 5-> 4-> 2-> 4 [5]

Таким образом, минимальные шаги равно 3.

Answer 1

Ваш код содержит «ошибка« один за другим ». Ваш цикл управляется range(2,n,1), то есть номерами от 2 до n-1 включительно, поэтому вы проиндексируете значения из списка memo[2] через memo[n-1] включительно. Но вы возвращаете свой результат от memo[n], который все еще имеет начальное значение 0.

Вы можете исправить эту ошибку с помощью этого for заявления:

for i in range(2,n+1,1): 

Кроме того, здесь другое решение:

import collections 

def minsteps(n): 
    memo = collections.defaultdict(lambda: n+1) 
    memo[1] = 0 
    for i in range(1, n+1): 
     memo[i+1] = min(memo[i+1], memo[i]+1) 
     memo[i*2] = min(memo[i*2], memo[i]+1) 
     memo[i*3] = min(memo[i*3], memo[i]+1) 
    return memo[n] 

for i in range(10): 
    print i, minsteps(i) 

Answer 2

Попробуйте это.

def minsteps1(n): 
    memo = [0]*(n+1) 
    def loop(n): 
     if n>1: 
      if memo[n]!=0: 
       return memo[n] 
      else: 
       memo[n] = 1 + loop(n-1) 
       if n%2 == 0: 
        memo[n] = min(memo[n], 1+loop(n//2)) 
       if n%3 == 0: 
        memo[n] = min(memo[n], 1+loop(n//3)) 
       return memo[n] 
     else: 
      return 0 
    return loop(n)