算法每日一练
💖今日学习💖
🥇数字三角形
🥈等差数列
🥉包子凑数
🥇1、数字三角形
🎯问题描述
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。
输入格式
输入的第一行包含一个整数N(1<N<=100)，表示三角形的行数。下面的N行给出数字三角形。数字三角形上的数都是 0至 100之间的整数。
输出格式
输出一个整数，表示答案。
样例输入
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5样例输出
27
package Day_Day_work;
import java.util.Scanner;
/**
* @author yx
* @date 2022-03-20 11:42
*/
public class dp打表法 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();//山的高度
int [][]arr=new int[n][n];
for (int i = 0; i <n ; i++) {
for (int j = 0; j <=i ; j++) {
arr[i][j]=scanner.nextInt();
}
}
int dp[][]=new int[n][n];
dp[n-1]=arr[n-1];//初始化dp数组的最后一行
for (int i = n-2; i >=0 ; i--) {
for (int j = 0; j <=i ; j++) {
dp[i][j]=arr[i][j]+Math.max(dp[i+1][j],dp[i+1][j+1]);//dp数组中的每一个位置都是当前更新的最大值
}
}
System.out.println(dp[0][0]);
}
}
dp打表法---题解分析 ：
（1）首先我们new一个dp二维数组，跟我们arr（存输入数据的数组）大小一致
（2）根据代码我们可以知道数组下标自上而下依次是递减的
（3）我们不妨从n-1层开始看（也就是最底层），dp数组的n-1层跟arr的n-1层一致
（4）开始更新dp数组的第n-2层，dp数组对应的每一个位置存储的都是当前更新的最大值
（5）自下而上，一直到dp[0][0],因为dp的每一层更新的都是最优值，所以最后dp[0][0]最优
package Day_Day_work;
import java.util.Scanner;
/**
* @author yx
* @date 2022-03-20 12:47
*/
public class 滚动数组解法 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int [][]arr=new int[n][n];//存的是输入进来的数组
int []dp=new int[n];//存的是当前最优的值
for (int i = 0; i <n ; i++) {
for (int j = 0; j <=i ; j++) {
arr[i][j]=scanner.nextInt();
}
}
dp=arr[n-1];
for (int i = n-2; i >=0 ; i++) {
for (int j = 0; j <=i ; j++) {
dp[j]=arr[i][j]+Math.max(dp[j],dp[j+1]);//更新当前的最优值并覆盖原来的值
}
}
System.out.println(dp[0]);
}
}
滚动数组法---题解分析 ：
（1）首先不知道大伙儿对滚动数组是否了解，简单点来说就是不断地更新一维数组中的值，这样就可以节省空间，有点状态压缩的感觉
（2）思路跟上面的打表法其实是差不多的，主要是对数组进行了降维处理，细心的朋友会发现数组由二维dp（打表法）变成了一维dp（滚动数组）
（3）更细心的朋友会联想到我们的背包问题，背包问题也是可以从二维降到一维的
🥈等差数列
🎯问题描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？输入格式
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A₁, A₂, · · · , AN。(注意 A₁ ∼ AN 并不一定是按等差数列中的顺序给出)输出格式
输出一个整数表示答案。
样例输入
5
2 6 4 10 20样例输出
10
样例说明
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。
package Day_Day_work;
import java.util.Arrays;
import java.util.Scanner;
/**
* @author yx
* @date 2022-03-12 19:22
*/
/*
需要考虑的情况
1、公差为0
2、公差为>=1
*/
public class 等差数列__gcd模板 {
static int min;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int[]A=new int[n];
int[]B=new int[n-1];
for(int i=0;i<n;i++){
A[i]=scanner.nextInt();
}
Arrays.sort(A);
for (int i = 0; i < n-1; i++) {
B[i]=A[i+1]-A[i];//求差值
}
min=gcd(B[0],B[1]);
for (int i = 1; i < n-2; i++) {//求公差的最大公约数
if (gcd(B[i], B[i + 1]) < min) {
min = gcd(B[i], B[i + 1]);//如果公差为0，则直接返回0
}
}
if(min==0){//公差为0的情况要放在for循环外面考虑
System.out.println(n);
return;
}
System.out.println((A[n-1]-A[0])/min+1);
}
static int gcd(int m,int n){//求最大公约数的模板
return n!=0 ? gcd(n,m%n): m;
}
}
题解分析 ：
（1）首先我们需要一个数组A用来存储输入的数据，对A进行排序
（2）其次我们需要一个数组B用来存储A数组两两之间的差值
（3）最后，我要来讲一下我们这道题目的坑
一号坑：A数组两两之间的最小差值并非我们的公差，例如：3，5，8；最小的差值为2，但是这三个数构成的等差数列其公差应该是1，所以这个地方我们需要对所有的差值求最大公约数（gcd）
二号坑：当我们求出公差d之后，我们的常规思路是将“（最大值-最小值）/d+1”,这个地方其实还有一个坑，就是我们的公差可以为0，而当d=0时不能做分母，最后提交的时候oj会显示“无效返回”，所以这个时候我们还需要将公差为0的情况单独拿出来讨论
🥉包子凑数
🎯问题描述
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。输入格式
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)输出格式
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。
例如，输入格式
2
4
5
程序应该输出：
6
再例如，输入格式
2
4
6
程序应该输出：
INF样例说明
对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
对于样例2，所有奇数都凑不出来，所以有无限多个。
package Day_Day_work;
import java.util.Scanner;
/**
* @author yx
* @date 2022-03-18 23:52
*/
//类似于”买不到的数目“
public class 包子凑数__dp打表法 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
boolean arr[]=new boolean[10200];//根据裴蜀定理得最大不能表示的数字位(ab-a-b)
int shuru[]=new int[n];
int g=0;
int answer=0;
arr[0]=true;
for (int i = 0; i < n; i++) {
shuru[i]=scanner.nextInt();
if (i==0)g=shuru[0];
else {
g=gcd(g,shuru[i]);
}
for (int j = 0; j < 10000; j++) {//打表法
if(arr[j]){
/*
因为0<=j<10000,0<shuru[i]<=100,所以这个地方解释了为什么arr[10200],防止溢出
状态压缩成一维数组
*/
arr[j+shuru[i]]=true;
}
}
}
if(g!=1){
System.out.println("INF");
return;
}
for (int i = 0; i < 10000; i++) {
if(!arr[i])answer++;
}
System.out.println(answer);
}
static int gcd(int m,int n){
return n!=0?gcd(n,m%n):m;
}
}
题解分析 ：
（1）这个问题困扰了博主好长时间，为了解决这个问题，博主也看了好多篇题解，也请教了许多博主朋友，他们大多数告诉我用“完全背包”去解这道问题，但我好像一直就没有get到这个题目的点，所以就很苦恼。然后，今天博主用另外一种很好理解的方法来带大家解这道题目。
（2）解这道题目，我们需要一个数论中裴蜀定理的知识：
1、两个数a，b如果互质（最大公约数为1），则它们最大不能组成的数为ab-a-b
2、如果两个数a,b不互质，则它们不能构成的数有无数多个
（老粉朋友们应该知道，博主在之前的一篇题解中就有提到这个数论知识）
（3）那我们现在来详细分析这道题目，首先我们将输入进来的数字进行互质判断（gcd最大公约数判断），将输入进来的数字进行两两公约数判断（最后得到的是这些数中的最大公约数），如果不为1则直接输出“INF”
（4）如果为1，我们要开辟一个大小为10200的boolea数组，这个就是该题非常巧妙的地方
1、为什么数组大小要为10200？
答：因为最大的不能表示的数为ab-a-b，因为a，b的范围在100以内，所以开10200就可以知道所有的情况了
2、开这个数组有什么用？
答：第一遍我们将第一个输入进来数所能表示的数，全部赋值为true，例如：输入2，则在10200内能表示的数有2、4、6、8......，再然后输入一个数，例如输入3，我们就对5（2+3），7（4+3）、9（6+3）....这些值进行赋值true,接下来就是同样的道理，最后对数组的每一个位置进行遍历，当遇到为false（表示当前的数字不能被表示）answer++ ，最后输出answer。
🚀写在最后
距离蓝桥杯正式省赛的时间越来越近了
你是否还在认真的备赛呢？
最后，送给大家一句话 “只要路是对的，就不害怕遥远”
- 点赞
- 收藏
- 关注作者
评论（0）