动态规划
动态规划三大题型：计数问题、最值问题、存在性问题；
【最小权值】-- 最值问题
【题目分析】
import java.util.Arrays;
Arrays类中的一个方法：Arrays.fill(int[] m,int n)
//给 int 类型(或者char类型/Long类型...)的数组全部空间填充上数字 n ；
Arrays.fill(int[] m,int start_index,int end_index,int n)
//在数组 m 的 start_index(包含该起始索引，可以取0)到 end_index(不包含该索引，最大到m.length) 填充数字n ;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.Arrays;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//从0-2021long[] dp = new long[2022];//dp储存的是不同结点数量时的最小权值Arrays.fill(dp,-1);//空子树权值是0 无根节点dp[0] = 0;//dp[1]是有一个结点(根结点)的最小权值dp[1] = 1;//i是该树所有结点的个数//i从2到2021for(int i=2;i<dp.length;i++){long min = Long.MAX_VALUE;//j=left 是该树左结点的个数//i-j-1=right 是该树的右结点for(int j=0;j<i;j++){int left = j;int right = i - j - 1; //1是根节点long temp = 1 + 2*dp[left] + 3*dp[right] + left*left*right;min = Math.min(min,temp);}dp[i] = min;}System.out.println(dp[2021]);scan.close();}
}【砝码称重】-- 计数问题
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int num = 0;//代表重量的种类//题目有提示N的范围[1,100] 总重量不超过100000int N = scan.nextInt();int[] w = new int[101]; //使用w[1]到w[100]//默认全是false;boolean[][] dp = new boolean[101][100001]; //使用[1...100]和[1...100000] long weight = 0L;for(int i = 1;i< N+1;i++){//初始化w[1]到w[N]w[i] = scan.nextInt();weight+=w[i];//所有情况中最大的砝码重量}/*核心代码*///放第i个砝码 i=1...Nfor(int i=1;i<N+1;i++){for(int j=1;j<=weight;j++){if(j==w[i]){dp[i][j] = true; //能够称出的重量赋T;//dp[0][1...max]在初始化的时候默认是F;}else{//设定放左边总重量减少 右边总重量增加//前 i 个砝码可以不可以称出 j ？考虑以下情况//1.如果dp[i-1][j]=T;上一个砝码已经可以称出 j 这个重量; 第 i 个砝码不放了;//2.dp[i-1][abs(j-w[i])]；上一个砝码(前i-1个)已经可以称出 j-w[i] ,那么第i个砝码(放右边)就可以称出 j 重量。dp[i][j]=T; //3.dp[i-1][j+w[i]]；上一个砝码(前i-1个)已经可以称出 j+w[i],那么第i个砝码(放左边)就可以称出 j 重量，dp[i][j]=T; dp[i][j] = dp[i-1][j] || dp[i-1][Math.abs(j-w[i])] || dp[i-1][j+w[i]];}}}for(int i=1;i<=weight;i++){if(dp[N][i]){num++;}}System.out.println(num);scan.close();}
}【序列】
package test;import java.math.BigInteger;
import java.util.HashSet;
import java.util.Scanner;
import java.util.*;
import java.lang.*;public class test2 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int N = scan.nextInt();int[] a = new int[N];int[] b = new int[N];int[] S = new int[N + 1];int sum = 0;for (int m : a) {m = scan.nextInt();}for(int i=0;i<N;i++) {a[i]=scan.nextInt();}int num = 0;// 首项&公差=jfor (int j = 1; j < N + 1; j++) {b[0] = j;//初始化数组bfor (int k = 1; k < N; k++) {b[k] = b[k - 1] + j;}for (int i = 0; i < N; i++) {if (b[i] % a[i] == 0) {num++;}}S[j] = num;num=0;}sum = 0;for (int i = 1; i < N + 1; i++) {sum += S[i];}System.out.println(sum);scan.close();}
}
【出栈次序】
n 个元素有多少种出栈顺序？
public class Main {// 不用管出站后车的数量和顺序，因为进站顺序和出站顺序已经决定出站时的排序static int fun(int a, int b) {// a是等待进站的数目，b是站中的数目if (a == 0)// 此时已全部进站，出站时的顺序只有一种return 1;if (b == 0)// 此时车站为空，只能让车进站return fun(a - 1, 1);// 有两种走法：1、让一辆车进站 ；2、让一辆车出站return fun(a - 1, b + 1) + fun(a, b - 1);}static int fun(int a) {return fun(a, 0);}public static void main(String[] args) {System.out.println(fun(16));}
}出栈顺序问题讲解 蓝桥杯_出栈序列-CSDN博客 请参考！
卡特兰数Catalan numbers
经典使用场景
1.合法的括号序列
2.二叉树形态计数
3.栈的出栈顺序
4.不同弦的相交
5.Dyck路径
6.凸多边形的三角划分
7.非交叉集合的划分
5. 卡特兰数（Catalan）公式、证明、代码、典例.-CSDN博客 参考！
//函数功能: 计算Catalan的第n项 //函数参数: n为项数 //返回值: 第n个Catalan数 int Catalan(int n) {if(n<=1) return 1;int *h = new int [n+1]; //保存临时结果h[0] = h[1] = 1; //h(0)和h(1)//第i项Cifor(int i=2;i<=n;++i) //依次计算h(2),h(3)...h(n){h[i] = 0;for(int j = 0; j < i; j++) //根据递归式计算 h(i)= h(0)*h(i-1)+h(1)*h(i-2) + ... + h(i-1)h(0)h[i] += (h[j] * h[i-1-j]);}int result = h[n]; //保存结果delete [] h; //注意释放空间return result; }
【居中输出】
//暴力解法import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int num(int m){int n = 0;//在计算数字的位数的时候需要考虑0 否则测试用例只能通过90%if(m==0){return 1;}while(m>0){m/=10;n++;}return n;}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int count = (10-num(n))/2;if(num(n)+count*2==10){for(int i=0;i<count;i++){System.out.printf("%c",'=');}System.out.printf("%d",n);for(int i=0;i<count;i++){System.out.printf("%c",'=');}}else{for(int i=0;i<count+1;i++){System.out.printf("%c",'=');}System.out.printf("%d",n);for(int i=0;i<count;i++){System.out.printf("%c",'=');}} scan.close();}
}【平方十位数】
import java.math.BigInteger;
import java.util.Scanner;
public class Main {static boolean sqrt_num1(long m) {// 不遗漏String s = m + "";int len = s.length();if (len != 10) {return false;}// 不重复：各个数位上的数字不重复int[] num = new int[10];for (int i = 0; i < 10; i++) {num[i] = 0;}while (m > 0) {//注意格式 (int)m%10 是把long型的数字限制在int的范围内 //而不是把（m%10）的结果由long转换为 intint last = (int) (m % 10); num[last]++;m /= 10;if (num[last] > 1) {return false;}}return true;}public static void main(String[] args) {Scanner scan = new Scanner(System.in);// 9876543210最大的数
// long big = 9876543210L;
// long a = (long) Math.sqrt(big);
// System.out.println(a); //a=99380;int flag = 0;for (long i = 99380; i > 0; i--) {long t = i * i;if (sqrt_num1(t)) {System.out.println(t);flag = 1;break;}if (flag == 1) {break;}}scan.close();}
}【神奇六位数】
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {//辅助boolean数组a[]static int[] six_num(int m){int[] arr = new int[10];for(int i=0;i<10;i++){arr[i] = 0;}while(m>0){int last =m%10;arr[last]++;m/=10;}return arr;} static boolean eq(int[] a,int[] b){for(int i=0;i<10;i++){if(a[i]!=b[i]){return false;}}return true;}public static void main(String[] args) {Scanner scan = new Scanner(System.in);//神奇六位数int start = 100000;int i=start;while(i<166666){int[] temp = six_num(i).clone();int j=2;int count = 0;while(j<7){int num = i*j;
// String str = num+"";
// //乘积的位数不是6位数
// if(str.length()!=6){
// j=8; //跳出循环
// }int[] arr = six_num(num).clone();if(eq(temp,arr)){j++;count++;}else {j=8;}}//不符合条件if(j==8){i++;}//正常跳出循环j==7if(j==7){System.out.println(i);i=166667;break;}}scan.close();}
}【前缀判断】
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static String start_with(String a,String b){//是否 a 包含了 b if(a.startsWith(b)){return a;}else{return "";}}static void test(String a,String b){String p =start_with(a,b);if(p==""&&b!=""){System.out.printf("[NO]\n");}else{System.out.printf("|%s|\n",p); }} public static void main(String[] args) {Scanner scan = new Scanner(System.in);test("abcd","abc");test("abcd","acb");test("abcd","abcd");test("abcd","abcd");test("","abc");test("","");scan.close();// System.out.println("".startsWith("abc"));}
}startsWith(String s); String对象的一个方法用来判断是否是前缀，返回值是布尔类型；
【最小公倍数和最大公因数】
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static void swap(int a,int b){int temp;temp = a;a = b;b = temp;} static void myfunc(int a,int b){int m,n,r;//辗转相除法//让第一个数字大if(a<b){swap(a,b);}//此时a>b m>n//m n 保留最初的两个数m = a;n = b;r = a%b;while(r!=0) {a = b;b = r;r = a%b;}//出来的时候说明r==0 即a能整除bSystem.out.printf("%d\n",b);//最大公约数System.out.printf("%d\n",b*(m/b)*(n/b)); //最小公倍数}public static void main(String[] args) {Scanner scan = new Scanner(System.in);myfunc(30,12);myfunc(12*7,30);scan.close();}
}
