python - 试图找到简单动态规划问题的重现

Question

我正在尝试解决这个问题:

Therasa is a Nurse. She wants to give some tablets to the patients in her practice. All the patients sit in a line and each of them has a rating score according to his or her health score. Therasa wants to give at least 1 tablet for each patient. Patients get jealous of their immediate neighbors, so if two patients sit next to each other then the one with the higher rating must get more tablets. Therasa wants to save money, so she wants to minimize the total number of tablets.

Input The first line of the input is an integer N, the number of patients in Therasa’s practice. Each of the following N lines contains an integer indicates the health score of each patient.

Output Output a single line containing the minimum number of tablets Therasa must give.

Constraints 1 <= N <= 100000 1 <= health score <= 100000

谁能给我一些关于 dp 循环的直觉？

我试过了，但它在某些测试用例上失败了

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

这里的问题是当患者 i 有更好的医疗保健但有更少(或相同)数量的药片时。在第一种情况下，您的条件是正确的，但您没有解决问题。在第二种情况下，您要确保患者 i 有更多的 table 。

与获得正确答案无关，我建议的另一项改进是替换这些:

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]