【蓝桥杯省赛】冲刺练习题【动态规划】倒计时【08】天
【摘要】 🙏🤗距离【第十三届蓝桥杯4月9日省赛】仅剩【08天】🤗🙏📋今日题型：【动态规划】(周新杰提供)📋⭐️🤗循环是一切暴力的基础，暴力基础，转起来。🤗⭐️🤗国一镇楼🤗📋比赛题目与分数比例📋确认范围：结果填空题5道，共计45分。程序设计题5道，共计105分。⭐️🤗刷题安排🤗⭐️日期题目类型题目数量3月25日循环63月26日超大数63月27日数组63月28日枚...
🙏🤗距离【第十三届蓝桥杯4月9日省赛】仅剩【08天】🤗🙏
📋今日题型：【动态规划】(周新杰提供)📋
⭐️🤗循环是一切暴力的基础，暴力基础，转起来。🤗⭐️
🤗国一镇楼🤗
📋比赛题目与分数比例📋
确认范围：
结果填空题5道，共计45分。
程序设计题5道，共计105分。
⭐️🤗刷题安排🤗⭐️
| 日期 | 题目类型 | 题目数量 |
| 3月25日 | 循环 | 6 |
| 3月26日 | 超大数 | 6 |
| 3月27日 | 数组 | 6 |
| 3月28日 | 枚举 | 6 |
| 3月29日 | 递归 | 6 |
| 3月30日 | 绘图 | 6 |
| 3月31日 | 深搜广搜 | 5 |
| 4月1日 | 动态规划 | 5 |
| 4月2日 | 填空题 | 5 |
| 4月3日 | 数学公式:查询准考证 | 5 |
| 4月4日 | 第十届省赛题 | 10 |
| 4月5日 | 第十一届省赛题 | 10 |
| 4月6日 | 第十二届省赛1套题 | 10 |
| 4月7日 | 第十二届省赛2套题 | 10 |
| 4月8日 | 经典题目练习 | 8 |
| 4月9日 | 9点考试 |
目录
1、三步问题
有个小孩正在上楼梯，楼梯有n阶台阶，小孩每次可以上1阶、两阶或者三阶。
计算小孩有多少种上楼梯的方式。结果可能很大，你需要对1000000007取模
样例输入
3样例输出
4样例输入
5样例输出
13范围
1<=n<=1000000
代码实现：
import java.util.Scanner;
public class dp_1 {
//三步问题
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] dp=new int[n+3];
dp[1]=1;
dp[2]=2;
dp[3]=4;
for (int i = 4; i <= n; i++) {
dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000007;
}
System.out.println(dp[n]);
}
}2、连续数列
给定一个整数数组，找出总和最大的连续数列
样例输入
[-2,1,-3,4,-1,2,1,-5,4]样例输出
6当连续的子数组为[4,-1,2,1]时最大
import java.util.Arrays;
import java.util.Scanner;
public class demo {
//连续数列
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
str=str.substring(1,str.length()-1);
String[] a=str.split(",");
int[] dp=new int[a.length];
//字符串数组转int数组
int[] s=Arrays.stream(a).mapToInt(Integer::parseInt).toArray();
dp[0]=s[0];
int max=s[0];
for (int i = 1; i < a.length; i++) {
dp[i]=Math.max(dp[i-1]+s[i], s[i]);
max=Math.max(max, dp[i]);
}
System.out.println(max);
}
}
3、打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
现在给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动报警装置的情况下，
能偷窃到的最高金额。
样例输入
[1,2,3,1]样例输出
4样例输入
[2,7,9,3,1]样例输出
12import java.util.Arrays;
import java.util.Scanner;
public class demo {
//打家劫舍
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
if(str.length()==0) {
System.out.println(0);
return;
}
if(str.length()==1) {
System.out.println(str);
return;
}
str=str.substring(1,str.length()-1);
String[] a=str.split(",");
int[] s=Arrays.stream(a).mapToInt(Integer::parseInt).toArray();
int[] dp=new int[a.length];
dp[0]=s[0];
dp[1]=Math.max(dp[0], s[1]);
for (int i = 2; i < a.length; i++) {
dp[i]=Math.max(dp[i-1], dp[i-2]+s[i]);
}
System.out.println(dp[s.length-1]);
}
}
4、不同路径
不同路径
一个机器人位于一个m*n网格的左上角机器人每次只能向下或者向右移动一步。
机器人视图达到网格的右下角，问总共有多少条不同的路径？
样例输入
3 2
样例输出
3样例输入
7 3样例输出
28代码实现
import java.util.Scanner;
public class demo {
//不同路径
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
int[][] dp=new int[m][n];
for (int i = 0; i < n; i++)dp[0][i]=1;
for (int i = 0; i < m; i++)dp[i][0]=1;
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[i].length; j++) {
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
System.out.println(dp[m-1][n-1]);
}
}5、最小路径和
最小路径和
给定一个包含非负数整数的m*n网格，请找出一条从左上角到右下角的路径，
使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入样例
3 3
1 3 1
1 5 1
4 2 1输出样例
7import java.util.Scanner;
public class dp_5 {
//最小路径和
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
int[][] a=new int[m][n];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
a[i][j]=sc.nextInt();
}
}
int[][] dp=new int[m][n];
dp[0][0]=a[0][0];
for (int i = 1; i < m; i++)dp[0][i]=dp[0][i-1]+a[0][i];
for (int i = 1; i < n; i++)dp[i][0]=dp[i-1][0]+a[i][0];
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp.length; j++) {
dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+a[i][j];
}
}
System.out.println(dp[m-1][n-1]);
}
}
附加题(超经典题目，建议不会的背下来公式)：
最长公共子序列
给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。
如果不存在公共子序列则返回0.
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不变字符串的相对顺序情况下删除某些字符后组成的新字符串。
例如“ace”是“abcde”的子序列，但是“aec”不是“abcde”的子序列
两个字符串公共子序列是这两个字符串所共同拥有的子序列。
样例输入
abcde
ace样例输出
3样例输入
abc
abc样例输出
3import java.util.Scanner;
public class dp_6 {
//最长公共子序列
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String text1=sc.nextLine();
String text2=sc.nextLine();
int[][] dp=new int[10000][10000];
for (int i = 1; i <= text1.length(); i++) {
for (int j = 1; j <= text2.length(); j++) {
if(text1.charAt(i-1)==text2.charAt(j-1)) {
dp[i][j]=dp[i-1][j-1]+1;
}else {
dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
System.out.println(dp[text1.length()][text2.length()]);
}
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）