青蛙过河问题python

青蛙过河问题是一道经典的动态规划问题，可以用Python来解决。该问题的描述是：一只青蛙想要过河，河流被分成了一系列的石头，青蛙可以跳到石头上，但不能跳进水中。给定一个数组stones，表示每个石头的位置，初始时青蛙在第一个石头上，青蛙每次可以跳跃的距离为上一次跳跃的距离加1或减1。要求判断青蛙是否能够到达最后一个石头。

以下是一种解决青蛙过河问题的Python代码示例：

def canCross(stones):
    # 创建一个字典，用于记录每个石头上的跳跃距离
    dp = {}
    for stone in stones:
        dp[stone] = set()

    # 初始化第一个石头的跳跃距离为0
    dp[stones[0]].add(0)

    # 遍历每个石头，计算当前石头上的跳跃距离
    for stone in stones:
        for step in dp[stone]:
            # 遍历当前石头的跳跃距离，计算下一步可能的跳跃距离
            for i in range(step - 1, step + 2):
                if i > 0 and stone + i in dp:
                    dp[stone + i].add(i)

    # 判断最后一个石头上是否有跳跃距离
    return len(dp[stones[-1]]) > 0

# 示例输入
stones = [0, 1, 3, 5, 6, 8, 12, 17]
print(canCross(stones))  # 输出：True

该代码使用动态规划的思想，通过一个字典dp来记录每个石头上的跳跃距离。首先初始化第一个石头的跳跃距离为0，然后遍历每个石头，计算当前石头上的跳跃距离。对于每个石头，遍历其跳跃距离，计算下一步可能的跳跃距离，并将其添加到下一个石头的跳跃距离集合中。最后判断最后一个石头上是否有跳跃距离，如果有则返回True，否则返回False。