前言
前段时间为了在面试中能够应对一些算法题走上了刷题之路，大多数都是在力扣平台刷，目前是300+，再加上到了新学校之后，了解到学校也有组织蓝桥杯相关的程序竞赛，打算再次尝试一下，就想系统学习一下算法（再此之前是主后端工程为主，算法了解不多刷过一小段时间），前段时间也是第一次访问acwing这个平台，感觉上面课程也是比较系统，平台上题量也很多，就打算跟着acwing的课程来走一段路，大家一起共勉加油！
目前是打算参加Java组，所以所有的题解都是Java。
本章节数学及简单dp的习题一览：包含所有题目的Java题解链接
例题的前三题是蓝桥杯关于数学内容；后三题是简单dp内容。
习题则是蓝桥杯题，相对于例题是进行了一个扩展。
例题：
AcWing 1205. 数学 买不到的数目 Java题解
AcWing 1211. 蚂蚁感冒 Java题解
AcWing 1216. 数学-蓝桥杯题 饮料换购 Java题解(模拟、数学)
AcWing 2. 动态规划-模板题 01背包问题 Java题解（二维数组、一维数组解法+图示）
AcWing 1015. 动态规划习题 摘花生 Java题解（二维数组、一维数组）
AcWing 4557. 动态规划-最长上升子序列 Java题解
习题：
AcWing 1212. 动态规划(路线+序列模型组合题) 地宫取宝 Java题解
AcWing 1214. 动态规划-蓝桥杯 波动数列 Java题解(详细推演)
其中背包问题（算法基础课）、摘花生(提高课)、最长子序列(提高课)
一、数学
蓝桥杯中的数学更像脑筋急转弯，涉及到一些数学的模型。
竞赛中的考察比较深的数学知识。
例题
例题1：AcWing 1205.买不到的数目【简单，蓝桥杯】
题目链接：1205. 买不到的数目
分析：若是不知道这个数学公式的话，只能通过先进行打表进行推举，或者按照思路2来进行从最大数往前进行推理。
解题：
暴力打表：暴力多组数据来最终去找规律
//包装中可能有的糖果数量n或m，求不能买到的糖果数量 import java.util.*; import java.io.*; class Main { private static int n, m; public static boolean dfs(int m, int p, int q){ if (m == 0) return true; if (m >= p && dfs(m - p, p, q)) return true; if (m >= q && dfs(m - q, p, q)) return true; return false; } public static void main(String[] args)throws Exception{ BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); String[] s = cin.readLine().split(" "); n = Integer.valueOf(s[0]); m = Integer.valueOf(s[1]); int res = 0; for (int i = Math.max(n, m); i <= 1000; i++) { if (!dfs(i, n, m)) res = i; } System.out.printf("%d\n", res); } }
思路1：公式一条解决
最终解决，实际上只需要使用一条公式即可：(p-1)*(q-1)-1
//包装中可能有的糖果数量n或m，求不能买到的糖果数量 import java.util.*; import java.io.*; class Main { private static int n, m; public static void main(String[] args)throws Exception{ BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); String[] s = cin.readLine().split(" "); n = Integer.valueOf(s[0]); m = Integer.valueOf(s[1]); System.out.printf("%d\n", (n - 1) * (m - 1) - 1); } }
思路2：从大到小进行推举
学习博客：AcWing 1205. 最简洁代码+详解
//包装中可能有的糖果数量n或m，求不能买到的糖果数量 import java.util.*; import java.io.*; class Main { private static int n, m; public static void main(String[] args)throws Exception{ BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); String[] s = cin.readLine().split(" "); n = Integer.valueOf(s[0]); m = Integer.valueOf(s[1]); //从最大的进行往前推 int k = n * m;//解必然在n*m下 while (k != 0) { int t = k; while (t % m != 0 && t - n > 0) t -= n; //此时t % m == 0 或者 t - n < 0 //该条件：①t % m != 0，表示筛选得到t - n < 0情况。②k不满足% n % m的情况 if (t % m != 0 && k % n != 0 && k % m != 0) { System.out.printf("t = %d, m = %d, n = %d\n", t, m, n); System.out.printf("%d", k); break; } k--; } } }
例题2：蚂蚁感冒【简单，蓝桥杯】
题目链接：1211. 蚂蚁感冒
分析：讨论情况题
统计位置为第一个右边 右向左(<0)，统计位置为第一个左边 左向右(>0)
两只蚂蚁碰面（灵魂互换继续向各自方向向前，且都感染）
题解：
import java.util.*; import java.io.*; class Main { private static final int N = 55; private static int n; private static int[] arr = new int[N]; public static void main(String[] args)throws Exception { BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); n = Integer.valueOf(cin.readLine()); String[] s = cin.readLine().split(" "); for (int i = 0; i < n; i++) { arr[i] = Integer.valueOf(s[i]); } int rightToLeft = 0, leftToRight = 0; for (int i = 1; i < n; i++) { //统计位置为第一个右边 右向左(<0) if (Math.abs(arr[i]) > Math.abs(arr[0]) && arr[i] < 0) rightToLeft++; //统计位置为第一个左边 左向右(>0) if (Math.abs(arr[i]) < Math.abs(arr[0]) && arr[i] > 0) leftToRight++; } //情况1：左右的蚂蚁必感染 //若是第一个蚂蚁向右 && 右边的蚂蚁向左的数量!=0 //若是第一个蚂蚁向左 && 左边的蚂蚁向右的数量!=0 //情况2：非情况1，此时感染蚂蚁的数量为1 if (arr[0] > 0 && rightToLeft != 0 || arr[0] < 0 && leftToRight != 0) { System.out.printf("%d", leftToRight + rightToLeft + 1); }else { System.out.printf("%d", 1); } } }
例题3：饮料换购【简单，蓝桥杯】
题目链接：1216. 饮料换购
题解：
思路1：模拟运算 复杂度：O(log3N) // n x count cnt // 啤酒数 喝完瓶盖数 换购 余下瓶盖 // 100 100 33 1 // 33 34 11 1 // 11 12 4 0 // 4 4 1 1 // 1 1 0 1 import java.util.*; import java.io.*; class Main { private static int n; public static void main(String[] args)throws Exception { BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); n = Integer.valueOf(cin.readLine()); int x = 0, count = 0, cnt = 0; int res = n;//初始为啤酒瓶盖数 while (n != 0) { x = n + cnt; count = x / 3; cnt = x % 3; res += count; n = count; } System.out.printf("%d", res); } }
思路2：数学
复杂度：时间复杂度O(1)
学习博客：【微扰理论】小学奥数题 ｜ 不用借酒瓶的那种
import java.util.*; import java.io.*; class Main { private static int n; public static void main(String[] args)throws Exception { BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); n = Integer.valueOf(cin.readLine()); //公式：瓶数n，每e个瓶盖换一瓶饮料 //n + (n - 1) / (e - 1) System.out.printf("%d", n + (n - 1) / (3 - 1)); } }
