青蛙跳格子 编程实现： 有 71 个大小相等的格子从左到右排成一排，编号从 0 到 70，其中 N 个格子有荷叶，初始时青蛙在编号为 0 的格子。青蛙要按照以下规则，跳到最后一个有荷叶的格子： 1、青蛙每次最少跳 1 格，最多跳 x 格； 2、青蛙每次只能跳到有荷叶的格子； 3、青蛙不能往回跳。 给定 N 个有荷叶的格子编号，以及青蛙每次最多可以跳的格子数 x。请计算青蛙一共有多少种不同的方式跳到最后一个有荷叶的格子，如果青蛙不能跳到最后一个有荷叶的格子，输出 0。 例如：N = 4，x = 3，4 个有荷叶的格子编号依次为 1、3、4、6，青蛙每次最多跳 3 格； 青蛙有以下不同的方式跳到最后一个有荷叶的格子（6 号格子）： 第一种：先跳到编号 1 的格子，接着跳到编号 3 的格子，再跳到编号 4 的格子，最后跳到编号 6 的格子； 第二种：先跳到编号 1 的格子，再跳到编号 3 的格子，最后跳到编号 6 的格子； 第三种：先跳到编号 1 的格子，再跳到编号 4 的格子，最后跳到编号 6 的格子； 第四种：先跳到编号 3 的格子，再跳到编号 4 的格子，最后跳到编号 6 的格子； 第五种：先跳到编号 3 的格子，最后跳到编号 6 的格子。 青蛙一共有 5 种不同的方式跳到最后一个有荷叶的格子。 输入描述： 第一行输入一个整数 N（3 ≤ N ≤ 30），表示有荷叶的格子数 第二行按从小到大的方式输入 N 个互不相同的整数（1 ≤ 整数 ≤ 70），表示有荷叶的格子编号，整数之间以一个空格隔开 第三行输入一个整数 x（1 ≤ x ≤ 5），表示青蛙每次最多可以跳的格子数 输出描述： 输出一个整数，表示青蛙一共有多少种不同的方式跳到最后一个有荷叶的格子 样例输入： 4 1 3 4 6 3 样例输出： 5
正确答案：DP。把荷叶位置排序（含起点0）。dp[0位置]=1；对每个荷叶位置p，dp[p]=sum(dp[q]) over前面荷叶q且1<=p-q<=x。答案=dp[最后荷叶位置]，不可达自然为0。
试卷来源：202403(第15届)蓝桥杯Python编程青少组(选拔赛_中/高级)真题