Самая большая сумма шагов по n ступеням
Это проблема домашней работы, и это DP, но это не "сколько способов решить проблему n-лестницы".
Скорее, в этой задаче каждому шагу лестницы присваивается номер от -10000 до 10000, поэтому, например, у меня есть такие шаги, как -1 2 1и я должен найти самую большую сумму, имея возможность подняться на один шаг или пропустить один шаг каждый раз. В этом примере этот ответ 3 так как я могу пропустить первый шаг, а затем просто посетить остальную часть лестницы.
Я замечаю, что всегда могу удалить последний шаг, так как в любом случае я должен наступить на него.
Как я могу сделать это в стиле динамического программирования? Нахожу ли я наибольшую сумму на каждом шаге?
4 ответа
Как вы знаете, динамическое программирование - это задание правильных вопросов.
Вопросы, которые следует задавать здесь с примером:
а = [-5, -2, 1, 3]
Какое максимальное значение вы можете получить, если вы наступите на 2 шага (индекс массива начинается с нуля), значение которого равно 1?
Давайте определим максимальное значение f [2], которое вы можете получить за 2 шага. Таким образом, у вас есть выбор там; либо вы можете наступить на него, либо не наступить на него.
If (step on 2 step in array index i.e 1)
you can also step on previous step i.e -2 or skip the previous step
if (you skip the previous step i.e -2)
you need to step on previous to previous step i.e -5
Сверху видно
f[2] = max(a[2] + a[1] or a[2] + a[0])
Я также учусь, поэтому я не уверен, правильно ли ниже или нет?
F [n] = max (F [n-1] + a [n], F [n-2] + a [n])
Установите массив целых чисел (или длинных или того, что будет содержать плюс или минус 10000*n) с именем sum[n]максимально возможная сумма, если вы стоите на ступеньке n, Обратите внимание, что sum[0]=step[0] является нулевым элементом массива, который вам дан, но sum[1]= max{0+step[1],sum[0]+step[1]} потому что вы можете достичь шага 1 либо прямо с пола, либо пройдя нулевой шаг. Теперь выясните аналогичную формулу для sum[2]и обобщить. Затем вычислите sum[i] с целью.
Я не думаю, что вы можете просто "удалить последний шаг". Возможно, вам придется наступить на это, и вы можете избежать этого, что бы ни было лучше. Возможно, вы захотите ввести фиктивный последний шаг со значением 0.
В дополнение к ответу ElKamina, помните, что независимо от того, что вы решите делать на любом этапе (один или два шага вперед), третий пункт оттуда доступен...
Просто подсказка:
Предположим, вы хотите достичь шага n. Вы можете перейти с шага n-2 или n-1.
Таким образом, F(n)= Макс (F(n-2),F(n-1)) + x[n]