我正在尝试解决这个问题：
Therasa是一名护士。她想在实践中给病人一些药片。所有的病人排成一排，每个人都有根据他或她的健康评分的评分。Therasa希望为每个患者提供至少1片。病人嫉妒自己的直系邻居，因此，如果两名病人相邻坐着，那么等级较高的一名病人就必须获得更多的药片。Therasa希望省钱，因此她希望最大限度地减少平板电脑的总数。
输入输入的第一行是整数N，即Therasa诊所的患者人数。接下来的N行中的每行都包含一个整数，指示每个患者的健康评分。
输出输出一行，其中包含Therasa必须提供的最小片剂数量。
约束1 <= N <= 100000 1 <=健康评分<= 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))
在最后一部分中（在反向移动时），您会犯一个小错误：
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的医疗保健量更大但药片的量较少（或相同）时。在第一种情况下，您的情况是正确的，但您没有解决问题。在第二种情况下，您要确保患者我有更多桌子。
与获得正确答案无关，我建议的另一项改进是替换这些：
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]
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句