【洛谷】P1424 小鱼的航程（改进版）

**小鱼的航程 (改进版)****题目描述**

小鱼在水面上游泳，需要经过 $n$ 个岛屿。每个岛屿都有一个坐标值，表示该岛屿与起点之间的距离。小鱼可以选择从当前岛屿跳跃到相邻的岛屿（即距离为1 的岛屿）。小鱼需要经过所有 $n$ 个岛屿，并且不能停留在任何一个岛屿上超过两次。

**问题**

给定 $n$ 个岛屿的坐标值，求出小鱼可以到达的最大岛屿数量。

**思路**

这个问题与传统的 "最长上升子序列" (LIS)问题类似，但是有一个关键差异：小鱼不能停留在任何一个岛屿上超过两次。因此，我们需要考虑到这一点，并且尽可能地减少跳跃次数。

**算法**

我们可以使用动态规划来解决这个问题。首先，我们定义一个数组 $dp$，其中 $dp[i]$ 表示小鱼经过第 $i$ 个岛屿后，可以到达的最大岛屿数量。

def max_island(n, islands):
 dp = [1] * n # 初始化 dp 数组 for i in range(1, n):
 for j in range(i):
 if abs(islands[i] - islands[j]) <=2: # 如果两个岛屿之间的距离不超过2 dp[i] = max(dp[i], dp[j] +1) # 更新 dp[i]

 return max(dp)

n =5islands = [1,3,6,8,10]
print(max_island(n, islands)) # 输出：4