Кузнечик Питон 18! выполняет серию прыжков по столбикам, расположенным в одной линии с равными расстояниями между ними
Кузнечик Питон 18! выполняет серию прыжков по столбикам, расположенным в одной линии с равными расстояниями между ними. Столбики пронумерованы от 1 до n. В начале, кузнечик находится на столбике 1. Он способен прыгать вперед на расстояние от 1 до k столбиков, считая от текущей позиции. Каждый столбик содержит определенное количество золотых монет (число золотых монет известно для каждого столбика). Определите наилучший способ прыжков для кузнечика, чтобы собрать максимальное количество золотых монет. Учтите, что кузнечик не может прыгать назад. Вводные данные в первой строке.
28.11.2023 10:53
Написать свой ответ:
Объяснение: Чтобы найти наилучший способ прыжков для кузнечика, нужно использовать динамическое программирование. Создадим массив dp, где dp[i] будет представлять максимальное количество золотых монет, которое можно собрать, достигнув столбика i. Изначально все элементы массива dp будут равны 0, кроме dp[1], которое будет содержать количество золотых монет на первом столбике.
Затем, для каждого столбика i от 2 до n, мы будем обновлять значение dp[i] следующим образом: dp[i] = max(dp[j] + золото_i), где j - предыдущий столбик, с которого можно достичь текущего столбика i с помощью прыжка.
Пройдемся по всем столбикам, начиная с 2, и обновим значения dp[i] с учетом предыдущих столбиков. В конце, ответом будет максимальное значение dp[n].
Дополнительный материал:
Вводные данные:
n = 6 (количество столбиков)
k = 3 (максимальное расстояние прыжка)
золото = [2, 5, 1, 3, 9, 4] (количество золотых монет на каждом столбике)
Решение:
Изначально dp = [0, 0, 0, 0, 0, 0, 0]
Обновляем значения dp:
dp[2] = max(dp[1]+золото[2]) = max(0+5) = 5
dp[3] = max(dp[1]+золото[3]) = max(0+1) = 1
dp[4] = max(dp[2]+золото[4], dp[3]+золото[4]) = max(5+3, 1+3) = 8
dp[5] = max(dp[2]+золото[5], dp[3]+золото[5], dp[4]+золото[5]) = max(5+9, 1+9, 8+9) = 14
dp[6] = max(dp[3]+золото[6], dp[4]+золото[6], dp[5]+золото[6]) = max(1+4, 8+4, 14+4) = 18
Ответ: максимальное количество золотых монет, которое можно собрать, равно 18.
Совет: Чтобы лучше понять задачу и решить ее, можно представить себя вместо кузнечика и пройти по всем столбикам, записывая текущее количество золотых монет для каждого столбика. Также полезно знание динамического программирования и его основных принципов.
Закрепляющее упражнение:
Вводные данные:
n = 10 (количество столбиков)
k = 4 (максимальное расстояние прыжка)
золото = [3, 1, 5, 2, 7, 4, 9, 8, 6, 2] (количество золотых монет на каждом столбике)
Каково максимальное количество золотых монет, которое можно собрать?