使用机器人可以开采一天的矿物,每天可以开采1gm或每天创建另一个机器人来度过一天-JPMC采访问题
例如:输入1输出1输入4输出3
机器人的最佳输出量完全取决于它可以工作多少天。我们可以很容易地得到最佳的复发率:
def optimal_output(days):
if days == 0: return 0
if days == 1: return 1
return max(optimal_output(days - 1) + 1, # Mine.
optimal_output(days - 1) + optimal_output(days - 2)) # Create robot.
我们可以看一下前几个术语:
>>> [optimal_output(n) for n in range(10)]
[0, 1, 2, 3, 5, 8, 13, 21, 34, 55]
[嘿,那只是斐波那契。这是有道理的,因为在第3天之后,我们得出optimal_output(days - 1) + 1
永远不会高于optimal_output(days - 1) + optimal_output(days - 2)
,而我们只剩下斐波那契的重复出现。