第十四届蓝桥杯集训——练习解题阶段(无序阶段)-dp练习2

​

 ​编辑

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-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];
	}

}

答案测试：

​编辑

答案正确，没问题。

总结

规律就是：事物之间的内在的本质联系。这种联系不断重复出现,在一定条件下经常起作用,并且决定着事物必然向着某种趋向发展。只要找到这个规律，没有什么难的题目。

​