Попытка найти повторение для простой задачи динамического программирования

Question

Я пытаюсь решить этот вопрос:

Тераза - медсестра. Она хочет дать пациентам несколько таблеток в своей практике. Все пациенты сидят в очереди, и у каждого из них есть оценка в соответствии с его или ее оценкой здоровья. Тераза хочет дать как минимум 1 таблетку для каждого пациента. Пациенты завидуют своим непосредственным соседям, поэтому, если два пациента сидят рядом, то пациент с более высоким рейтингом должен получить больше таблеток. Тераза хочет сэкономить, поэтому она хочет свести к минимуму общее количество таблеток.

Входные данные В первой строке входных данных указано целое число N - количество пациентов в практике Теразы. Каждая из следующих N строк содержит целое число, указывающее оценку состояния здоровья каждого пациента.

Выходные данные Выведите одну строку, содержащую минимальное количество таблеток, которые должна дать Тераза.

Ограничения 1 <= N <= 100000 1 <= показатель здоровья <= 100000 </p>

Может ли кто-нибудь дать мне некоторую интуицию для повторения дп?

Я пытался это сделать, но в некоторых тестовых случаях это не удалось

n = int(input())
h = []
for i in range(n):
    x = int(input())
    h.append(x)

dp  = [0] * len(h)
dp[0] = 1

for i in range(1, len(h)):
    if h[i] > h[i-1]:
        dp[i] = dp[i-1] + 1
    else:
        dp[i] = 1 

for i in range(len(h)-2, -1, -1):
    if h[i]>=h[i+1] and dp[i]<=dp[i+1]:
        dp[i] = dp[i+1]

print(sum(dp))

Answer 1

В последней части (при обходе в обратном направлении) у вас есть небольшая ошибка:

for i in range(len(h)-2, -1, -1):
    if h[i]>=h[i+1] and dp[i]<=dp[i+1]:
        dp[i] = dp[i+1]

должно быть:

for i in range(len(h)-2, -1, -1):
    if h[i]>h[i+1] and dp[i]<=dp[i+1]:
        dp[i] = dp[i+1] + 1

Проблема здесь в том, что у пациента больше здоровьяно имеет меньшее (или такое же) количество таблеток. В первом случае ваше состояние верно, но вы не решаете проблему. Во втором случае вы проверяете, есть ли у пациента больше таблиц.

Не имеет значения, чтобы получить правильный ответ, я бы предложил еще одно улучшение, заменив их:

dp  = [0] * len(h)
dp[0] = 1

for i in range(1, len(h)):
    if h[i] > h[i-1]:
        dp[i] = dp[i-1] + 1
    else:
        dp[i] = 1 

на эти:

dp  = [1] * len(h)

for i in range(1, len(h)):
    if h[i] > h[i-1]:
        dp[i] = dp[i-1] + 1

Поскольку мы знаем, что каждый пациент получит как минимум 1 таблетку.

Обновление: Вот пример случая, когда ваш первыйкод потерпит неудачу:
h = [10, 10, 1]
Ваш код будет рассчитывать dp = [1, 1, 1]