2023年12月16日发(作者：)

旋转寿司算法题

今天我们来看一个有趣的算法题，它的主题是旋转寿司。

题目描述：

有一家旋转寿司店，它会有 n 盘寿司在旋转带上依次经过你的面前。你可以选择其中的任意一盘寿司，但不可以选择相邻的两盘寿司。你需要设计一种算法，使得你选择的寿司的总价值最大。

输入：

第一行输入一个整数 n，表示有 n 盘寿司。

接下来的一行输入 n 个整数，分别表示每一盘寿司的价值。

输出：

输出一个整数，表示你选择的寿司的总价值最大值。

样例输入：

5

2 7 9 3 1

样例输出：

12

提示：

对于 100% 的数据，1 ≤ n ≤ 1000，0 ≤ 价值 ≤ 10000。

解题思路：

这道题可以通过动态规划来解决。

我们定义 dp[i] 表示到第 i 盘寿司时选择的总价值最大值。那么对于每一盘寿司，我们有两种选择：选择这一盘或者不选择这一盘。

- 1 -

如果选择这一盘，那么前一盘就不能选择，所以总价值为 dp[i-2]

+ v[i]。

如果不选择这一盘，那么总价值就是 dp[i-1]。

取这两个值的较大值即为 dp[i] 的值。

最终答案即为 dp[n]，表示到第 n 盘寿司时选择的总价值最大值。

- 2 -