Задача в Пайтон
Однажды кузнечик, как обычно, гулял по лугу. Он наткнулся на цепь. Его интересовал
один вопрос — какой минимальный навык прыжка ему нужен, чтобы дойти до конца
цепочки. Обратите внимание, что цепочка состоит только из заглавных английских букв, и
кузнечик может прыгать только на гласные в цепочке.
В начале кузнечик стоит слева от крайнего левого символа в цепочке, и его цель —
попасть в ячейку прямо справа от самого правого символа. За один прыжок кузнечик
может прыгнуть на любое расстояние от 1 до своего навыка прыжка. Давайте посмотрим
на картинку ниже для ясности.
Примечание: Гласные буквы это ′′, ′′, ′′, ′′, ′′ и ′′ .
Входные данные
В единственной строке даётся строка , состоящая из заглавных английский букв.
Выходные данные
Выведите целое число — минимальную прыгучесть кузнечика.
Ответы на вопрос
Ответ:
Чтобы решить эту задачу, мы можем использовать подход поиска в ширину (breadth-first search).
Сначала мы создаем очередь и добавляем в нее текущую позицию кузнечика (позиция 0, так как он стоит слева от крайнего левого символа). Затем мы итерируемся по очереди, берем текущую позицию из очереди и проверяем, может ли кузнечик прыгнуть на следующий символ с помощью текущего навыка прыжка. Если да, то мы добавляем эту позицию в очередь. Если мы дошли до конца цепочки, то мы выводим текущий навык прыжка и завершаем программу. Если очередь оказалась пустой, значит, кузнечику не удалось добраться до конца цепочки с любым навыком прыжка, поэтому мы выводим -1.
Вот как это может выглядеть в коде:
def min_jump(chain):
queue = []
queue.append
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]