最近的一些文章都可能会很碎,写到哪里是哪里,过一阵子会具体的整理一遍,这里其它的类型题先往后排一排,因为蓝桥最后考的也就是对题目逻辑的理解能力,也就是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];
}
}
答案测试:
答案正确,没问题。
规律就是:事物之间的内在的本质联系。这种联系不断重复出现,在一定条件下经常起作用,并且决定着事物必然向着某种趋向发展。只要找到这个规律,没有什么难的题目。