有一排香蕉,每个香蕉有不同的甜度值。小猴子想吃香蕉,但不能吃相邻的香蕉。以下代码能找到小猴子吃到甜甜的香蕉组合。
def find_selected_bananas(bananas, dp):
selected = []
i = len(bananas) - 1
while i >= 0:
if i == 0:
selected.append(0)
break
if dp[i] == dp[i-1]:
i -= 1
else:
selected.append(i)
i -= 2
selected.reverse()
print("小猴子吃了第", end="")
for idx in selected:
print(idx + 1, end=" ")
print("个香蕉")
def main():
bananas = [1, 2, 3, 1] # 每个香蕉的甜度
if not bananas:
return
n = len(bananas)
dp = [0] * n
dp[0] = bananas[0]
if n > 1:
dp[1] = max(bananas[0], bananas[1])
for i in range(2, n):
dp[i] = max(bananas[i] + dp[i-2], dp[i-1])
find_selected_bananas(bananas, dp)
正确
错误