Блог

Главная - Вопросы по программированию - Проблема подхода к динамическому программированию

Проблема подхода к динамическому программированию

#python #combinations #dynamic-programming #permutation

Вопрос:

Алиса каждый день бегает трусцой на N метров. Иногда она бегает, а иногда идет пешком. Ее скорость ходьбы составляет 1 м/с, а скорость бега-2 м/с. Учитывая расстояние, до которого она совершает пробежку, рассчитайте количество способов, которыми она может совершать пробежку.

пример:

Вход: 3 (общее пройденное расстояние во время бега трусцой)

Вывод: 3 (возможный случай)

Пояснение: Алиса могла бегать трусцой 3 способами

  1. Алиса проходит 3 метра
  2. Алиса пробежала 2 метра, а затем прошла 1 м
  3. Алиса проходит 1 м, а затем бежит 2 м

Пример 2:

Вход: 4

Выход: 5

Пояснение: Алиса могла бегать трусцой 5 способами

  1. Алиса пройдите все 4 метра
  2. Алиса сначала идет 2 метра, а затем бежит 2 метра
  3. Алиса могла пробежать 2 метра, а затем пройти 2 метра
  4. Алиса пройди 1 метр, а затем пробежи 2 метра, а затем пройди 1 метр
  5. Алиса пробежала все 4 метра

Я решил приведенную выше постановку проблемы, используя следующий код

 
from itertools import permutations

n = int(input())

c = 0
t = [2]*(n//2)
if n % 2 != 0:
    t = t [1]

for i in range(t.count(2)):
    c = c len(set(list(permutations(t, len(t)))))
    t.remove(2)
    t.append(1)
    t.append(1)
c = c len(set(list(permutations(t, len(t)))))
print(c)

Я новичок в динамическом программировании, кто-нибудь может мне помочь ? как я могу реализовать это в методе динамического подхода и добиться более оптимальной сложности по времени?

Большое вам спасибо за ваше ценное отношение к моей проблеме.

Комментарии:

1. Я не понимаю постановки проблемы. Алиса должна выбрать количество a метров для ходьбы и количество b метров для бега, чтобы a b=N ? Есть только N 1 возможности. Здесь не нужен какой-либо алгоритм, просто вернитесь N 1 .

2. Я не понимаю примера, который вы приводите. Почему вывод 3 , а не 4 в этом случае? Вы игнорируете решение, в котором Алиса пробегает 3 метра?

3. «Ее скорость ходьбы составляет 1 м/с, а скорость бега-2 м/с.» Имеет ли эта информация какое-либо отношение к проблеме? Как?

4. Похоже, что вопрос такой же, как «сколько способов подняться по N ступеням, делая по 1 или 2 шага за раз», на который ответ-fib(N 1)

5. Недостающей частью вопроса, по-видимому, является неписаное предположение о том, что Алиса может переключаться между ходьбой и бегом только на границах целых секунд.

Ответ №1:

Вдохновленный всеми предыдущими постами и подтвержденными неписаными предположениями, это всего лишь еще один вопрос о последовательности выдумок.

Титры ко всем предыдущим плакатам. (код тогда довольно прост) Просто для справки — надеюсь, это поможет.

 def jogging_ways(n: int) -> int:
    # f(3) = f(1)   f(2)
    a, b = 1, 1
        
    for i in range(n):
        a, b = b, a b
        #print(a, b)
        
    return a

Выполняется:

 > jogging_ways(4)
  5
> jogging_ways(5) 
  8
Метки: