第十四届蓝桥杯集训——练习解题阶段(无序阶段)-dp练习2
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。
题目：蓝桥杯-算法提高-超级玛丽
问题描述
大家都知道"超级玛丽"是一个很善于跳跃的探险家，他的拿手好戏是跳跃，但它一次只能向前跳一步或两步。有一次，他要经过一条长为n的羊肠小道，小道中有m个陷阱，这些陷阱都位于整数位置，分别是a 1,a 2,....a m，陷入其中则必死无疑。
显然，如果有两个挨着的陷阱，则玛丽是无论如何也跳过不去的。 现在给出小道的长度n，陷阱的个数及位置。
求出玛丽从位置1开始，有多少种跳跃方法能到达胜利的彼岸（到达位置n）。
输入格式 第一行为两个整数n,m 第二行为m个整数，表示陷阱的位置 输出格式 一个整数，表示玛丽跳到n的方案数。
样例输入
4 1
2
样例输出
1
数据规模和约定【40>=n>=3,m>=1 n>m】陷阱不会位于1及n上。
题解：
这类题目相对来说很容易分析，就是+1+2的区别，一步两步，有规定的，故而只要不是地雷我们就按照斐波那契数列的规律加就行了，但是这里对起始位置我们要计算好，从1开始。
不过我们需要单独创建雷区与对应累加数字的数组dp，不然就计算很麻烦了，我捉摸了一项能否免去创建，使用一个数组，但是没想到什么好的方法，您可以自己想想办法，如何能让这个程序更简洁一些。
package com.item.action; import java.util.Scanner; public class Demo3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();// 长度 int m = sc.nextInt();// 陷阱个数 int a[] = new int[n];// 雷区带下标1 for (int i = 0; i < m; i++) { int index = sc.nextInt(); a[index] = 1;// 有雷就是1 } sc.close(); int result = fun(n, a); System.out.println(result); } private static int fun(int n, int[] arr) { int[] dp = new int[n]; dp[0] = 0; dp[1] = 1; for (int i = 2; i < n; i++) { if (arr[i] != 1) { //不是雷就累加 dp[i] = dp[i - 1] + dp[i - 2]; } } return dp[n - 1]; } }
答案测试：
答案正确，没问题。
总结
规律就是：事物之间的内在的本质联系。这种联系不断重复出现,在一定条件下经常起作用,并且决定着事物必然向着某种趋向发展。只要找到这个规律，没有什么难的题目。
