蓝桥杯青蛙过河（动态规划）_蓝桥青蛙

1. 问题描述：

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

输入格式

第一行有一个正整数L（1 <= L <= 10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

输出格式

输出格式 只包括一个整数，表示青蛙过河最少需要踩到的石子数。

样例输入

10
2 3 5
2 3 5 6 7

样例输出

2

【数据规模】 对于30%的数据，L <= 10000； 对于全部的数据，L <= 10^9。

来源：https://www.luogu.com.cn/problem/P1052

2. 思路分析：

① 这道题目与力扣中一道跳跃游戏的题目是很类似，仔细分析可以知道其实本质上都是一样的，都是需要计算从起始位置到目标位置经过的路径中某些变量的最小值，对于这一类题目经典的做法是动态规划，其中比较容易想到的思路记录到达当前位置i经过的最少的石头数目，基于这个想法我们可以声明一个长度为L的dp列表，当前我的位置为i，那么上一次的位置范围就为i - j：[i - T, i - S]，我们需要从这个范围中找出能够到达当前位置i的上一个位置i - j对应的dp[i - j]的最小值，这样就可以求解出从上一个位置中的dp列表的最小值推导出到达当前位置i踩到的最少石头数目，这样一直推导到桥的最后的位置那么就可以知道从起始位置到达目标位置踩的最少的石头数目，但是由于L最大为10^9所以当数据量比较大的时候还是通不过的，需要进行进一步的优化才可以

② 先记录一下最容易想到的动态规划的思路，后面学习到对动态规划的优化再补充一下博客，可以在洛谷上提交一下代码验证是否正确，下面的代码是得了27分，对了四个数据

3. 代码如下：

import sys
import collections
if __name__ == '__main__':
    L = int(input())
    # S, T分别表示青蛙能够跳跃的最小距离与最大距离, M为桥上的石头数目
    S, T, M = map(int, input().split())
    # 桥上石头的位置
    stonesPos = list(map(int, input().split()))
    dp = [sys.maxsize] * L
    dp[0] = 0
    # 将这些石头位置的存储在字典中会更方便查询出来
    dic = collections.defaultdict(int)
    for i in stonesPos:
        dic[i] += 1
    for i in range(1, L):
        for j in range(S, T + 1):
            # 无法通过上一个步骤到达当前的i位置则break
            if i - j < 0: break
            elif dp[i - j] != sys.maxsize:
                # 检查上一步到i这个位置是否存在石头如果存在石头那么就需要加1否则不加1
                if i in dic:
                    dp[i] = min(dp[i], dp[i - j] + 1)
                else:
                    dp[i] = min(dp[i], dp[i - j])
    print(dp[-1])