動態規劃
動態規劃三大題型：計數問題、最值問題、存在性問題；
【最小權值】-- 最值問題
【題目分析】
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();}
}
)
)
)
)
)
)
