forked from Gitlink/forgeplus
29 lines
715 B
Python
29 lines
715 B
Python
def coin_amount(c):
|
|
table = [0, c[0]] # 开头放一个0以便直接进行比较
|
|
for i in range(2, len(c) + 1):
|
|
table.append(max(table[i - 2] + c[i - 1], table[i - 1]))
|
|
return table
|
|
|
|
|
|
def back(table, c):
|
|
collected_coins = []
|
|
lent = len(table) - 1
|
|
i = lent
|
|
while i >= 1:
|
|
if table[i] > table[i - 1]: # 选最后一个
|
|
collected_coins.append(c[i - 1])
|
|
i -= 2
|
|
else:
|
|
i -= 1
|
|
return collected_coins
|
|
|
|
|
|
if __name__ == "__main__":
|
|
c = [5, 1, 2, 10, 6, 2]
|
|
temp = coin_amount(c)
|
|
collected_coins = back(temp, c)
|
|
print("动态规划表：")
|
|
print(temp)
|
|
print("最大序列：")
|
|
print(collected_coins[::-1])
|