shenwanqin

用户名：dotcpp0734246

访问量：72

签　名：

等　　级
排　　名	23579
经　　验	641
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校	江苏大学
专　　业

　　自我简介：

TA的其他文章

java两种方式题解动态规划、深度搜索（题目测试数据有坑，输入数据中有大于n的数据，会导致数组越界）
浏览：28

你可能喜欢

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

java两种方式题解动态规划、深度搜索（题目测试数据有坑，输入数据中有大于n的数据，会导致数组越界）

　　作者: shenwanqin　　　　发表时间：2024-03-05 17:24:13 浏览：28　|　评论：0　

原题链接：蓝桥杯算法提高VIP-超级玛丽

import java.util.*;

public class Main {   //1567
 
	public static void main(String[] args) {
		// 到达位置为x的地方有多少种方法
		
		Scanner scanner = new Scanner(System.in);    //普通动态规划解法
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int[] dp = new int[n + 1];
		Arrays.fill(dp, 1);
		for (int i = 1; i <= m; i++) {
			int index = scanner.nextInt();
			if(index<n) dp[index] = 0;   //代表此处是陷阱
		}
		if (dp[1] == 0 || dp[n] == 0)
			System.out.print(0);
		else {

for (int i = 3; i <= n; i++) {
				if (dp[i] == 0) {
					if (dp[i + 1] == 0) {
						System.out.print(0);
						break;
					}
					continue;
				} else {
					if (dp[i - 1] == 0 && dp[i - 2] != 0) {
						dp[i] = dp[i - 2];
						continue;
					}
					if (dp[i - 2] == 0 && dp[i - 1] != 0) {
						dp[i] = dp[i - 1];
						continue;
					}
					dp[i] = dp[i - 1] + dp[i - 2];
				}
			}
			System.out.print(dp[n]);
		}   
		
	/*	  
		Scanner scanner = new Scanner(System.in);   //dfs解法
		int n = scanner.nextInt();   //路的长度
		int m = scanner.nextInt();   //陷阱的个数
		int []a = new int[n+1];
		
		for(int i = 0;i<m;i++) {
			int index = scanner.nextInt();
			if(index<n) a[index] = 1;   //代表此处是陷阱
		}
		dfs(1, a, n);
		System.out.print(result);
	}
	static int result = 0;
	public static void dfs(int i,int []a,int n) {
		if(i == n) {
			result++;
			return;
		}
		if(i >= n) return;
		if(a[i]==1) return;
		dfs(i+1,a,n);
		dfs(i+2,a,n);
	}  */
	}
}

0.0分

1 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

shenwanqin

TA的其他文章

你可能喜欢

C语言训练-字符串正反连接（C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

矩形面积交（Java代码）

java两种方式题解动态规划、深度搜索（题目测试数据有坑，输入数据中有大于n的数据，会导致数组越界）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C++代码）

C二级辅导-阶乘数列（C++代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

点我有惊喜！你懂得！

C语言考试练习题_保留字母（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

钟神赛车（C++代码）

WU-格式化数据输出（C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

shenwanqin

TA的其他文章

你可能喜欢

C语言训练-字符串正反连接 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

矩形面积交 （Java代码）

java两种方式题解 动态规划、深度搜索（题目测试数据有坑，输入数据中有大于n的数据，会导致数组越界）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C++代码）

C二级辅导-阶乘数列 （C++代码）

C语言训练-8除不尽的数 （C语言代码）暴力解法，答案只有一个，直接输出就好了

点我有惊喜！你懂得！

C语言考试练习题_保留字母 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

钟神赛车 （C++代码）

WU-格式化数据输出 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言训练-字符串正反连接（C语言代码）

矩形面积交（Java代码）

java两种方式题解动态规划、深度搜索（题目测试数据有坑，输入数据中有大于n的数据，会导致数组越界）

　　评论区

C二级辅导-阶乘数列（C++代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言考试练习题_保留字母（C语言代码）

钟神赛车（C++代码）

WU-格式化数据输出（C语言代码）