Блог

Я пытаюсь решить проблему, приведенную ниже: (Я решил ее с помощью рекурсии, но мне трудно пытаться использовать кеш, чтобы предотвратить пересчет множества одинаковых шагов. «»» Учитывая положительное целое число N, найдите наименьшее количество шагов, которое потребуется для достижения 1.

Существует два вида разрешенных шагов:

Вы можете уменьшить N до N — 1. Если a * b = N, вы можете уменьшить N до большего из a и b.

Например, при заданном 100 вы можете достичь 1 за пять шагов по следующему маршруту: 100 -> 10 -> 9 -> 3 -> 2 -> 1. «»»

 def multiples(num):
    ret = []
    start = 2
    while start < num:
        if num % start == 0:
            ret.append(num // start)
        start  =1
        if ret and start >= ret[-1]:
            break
    return ret if ret else None
 

 def min_jumps_no_cache(num, jumps=0):
    if num == 1:
        return jumps
    
    mults = multiples(num)
    res = []
    res.append(min_jumps(num - 1, jumps  1))
    if mults:
        for mult in mults:
            res.append(min_jumps(mult , jumps  1))
    return min(res)
 

Теперь я пытаюсь добавить сюда кэш из-за очевидного высокого времени выполнения этого решения. Но я уже сталкивался с подобной проблемой раньше, когда я перезаписывал кеш, и мне было любопытно, есть ли решение для этого.

 def min_jumps_cache(num, jumps=0, cache={}):

    if num == 1:
        return jumps
    if num in cache:
        return cache[num]
    
    mults = multiples(num)
    res = []
    
    temp = min_jumps_cache(num - 1, jumps  1, cache)
    res.append(temp)
    if mults:
        for mult in mults:
            res.append(min_jumps_cache(mult , jumps  1, cache))
    temp = min(res)
    cache[num] = min(temp, cache[num]) if num in cache else temp
    return temp
 

Мне кажется, проблема здесь в том, что вы не можете действительно кэшировать ответ, пока не рассчитаете оба его «левого и правого» решения, чтобы найти ответ. Есть ли что-то еще, чего мне здесь не хватает?

Ваше решение в порядке, насколько это возможно.

Однако будет более эффективно выполнять решение в ширину снизу вверх. (Это может быть тривиально оптимизировано больше. Как упражнение для читателя.)

 def path (n):
    path_from = {}
    queue = [(1, None)]
    while True:
        value, prev = queue.pop(0)
        value not in path_from:
            path_from[value] = prev
            if value == n:
                break # EXIT HERE
            queue.append((value 1, value))
            for i in range(2, min(value 1, n//value   1)):
                queue.append((i*value, value))

    answer = []
    while n is not None:
        answer.append(n)
        n = path_from[n]

    return(answer)

print(path(100))