Question

Задача в Пайтон
Однажды кузнечик, как обычно, гулял по лугу. Он наткнулся на цепь. Его интересовал
один вопрос — какой минимальный навык прыжка ему нужен, чтобы дойти до конца
цепочки. Обратите внимание, что цепочка состоит только из заглавных английских букв, и
кузнечик может прыгать только на гласные в цепочке.
В начале кузнечик стоит слева от крайнего левого символа в цепочке, и его цель —
попасть в ячейку прямо справа от самого правого символа. За один прыжок кузнечик
может прыгнуть на любое расстояние от 1 до своего навыка прыжка. Давайте посмотрим
на картинку ниже для ясности.
Примечание: Гласные буквы это ′′, ′′, ′′, ′′, ′′ и ′′ .
Входные данные
В единственной строке даётся строка , состоящая из заглавных английский букв.
Выходные данные
Выведите целое число — минимальную прыгучесть кузнечика.

Answer 1

Ответ:

Чтобы решить эту задачу, мы можем использовать подход поиска в ширину (breadth-first search).

Сначала мы создаем очередь и добавляем в нее текущую позицию кузнечика (позиция 0, так как он стоит слева от крайнего левого символа). Затем мы итерируемся по очереди, берем текущую позицию из очереди и проверяем, может ли кузнечик прыгнуть на следующий символ с помощью текущего навыка прыжка. Если да, то мы добавляем эту позицию в очередь. Если мы дошли до конца цепочки, то мы выводим текущий навык прыжка и завершаем программу. Если очередь оказалась пустой, значит, кузнечику не удалось добраться до конца цепочки с любым навыком прыжка, поэтому мы выводим -1.

Вот как это может выглядеть в коде:

def min_jump(chain):

queue = []

queue.append

Answer 2

def min_jump(s):

   # Создаем двумерный массив dp

   n = len(s)

   dp = [[float('inf')] * n for _ in range(n)]

   # Заполняем массив dp

   for i in range(n):

       for j in range(i, n):

           # Если текущий символ в цепочке является гласной буквой,

           # то мы можем прыгать на эту позицию

           if s[j] in 'AEIOU':

               # Если i == j, то нам не нужно никуда прыгать

               if i == j:

                   dp[i][j] = 0

               else:

                   # Иначе, мы ищем минимальную прыгучесть, необходимую для достижения этой позиции

dp[i][j] = min(dp[i][k] + 1 for k in range(i, j))

# Возвращаем минимальную прыгучесть, необходимую для достижения конца цепочки

return dp[0][n - 1]