题目描述

塔子哥小时候很喜欢一个叫跳格子的游戏，地上总共有$n$几个格子，塔子哥跳到第$i$个格子可以获得$a_i$的分数。 塔子哥从第1个格子开始，塔子哥每次可以跳跃一个悲波那契数的长度，她想知道她恰好跳到第$n$个格子最多可以获得多少分。 所谓斐波那契数，指斐波那契数列:1,1,2,3,5,8.….中的某一项。悲波那契数列满足，第三项开始，每一项等于前两项之和。

题解

题目要求到从第 $1$ 个格子跳到第 $n$ 个格子所能获得的最大分数，每次跳跃的距离必须是一个斐波那契数。

非常经典的一类 DP 题目了，定义 $dp[i]$表示跳到第 $i$ 个格子所能获得的最大分数。

显然，$dp[0] = w[0]$

• 对于$dp[i] (i > 0)$，可以枚举上一步跳跃的距离 $val$，如果 $val$ 是一个斐波那契数，并且 $i - val >= 0$，那么可以从第 $i - val$ 个格子跳到第 $i$ 个格子，此时获得的分数为 $dp[i - val] + w[i]$