洛谷官方题单[Java版题解]--【算法1-4】递推与递归

知识点:高精度递归Java版:高精度讲解这里BigInteger.ONE 是你创建了一个BigInteger的类型的c,然后值给它赋值为了1这里的3.比较如果是负数返回-1,如果是相等返回0,如果是正数返回1本题的详解,因为本题的数据给的是n5000最后结果长度会是一个天文数字,所以必须用高精度(BigInteger),然后如果是普通的递归斐波那契,时间复杂度是n的2次方,n如果超过10绝逼会超时package love8; import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); //现在你学了IO流后去看这个Scanner,不就是一个打印流吗 //为了防止资源一直被占用,还是要去手动关流 sc.close(); if(n1) { System.out.println(1); return; } if(n2) { System.out.println(2); return; } //为了防止最后结果数字太大,超过int或者long类型,所以最后还是去用BigInteger BigInteger aBigInteger.ONE; BigInteger bBigInteger.TWO; BigInteger cBigInteger.ZERO; for(int i3;in;i){ ca.add(b); ab; bc; } System.out.println(c); //我发现这个瞬间就跑完了 //因为以前如果是递归斐波那契的话,时间复杂度是2的n次方,5000回跑到宇宙毁灭 } }知识点:递归记忆化:所谓记忆化,简单来说,就是去把每个数据保存下来,下次要用就直接不去算了为什么要去用记忆化:因为假如你要算的东西特别大,里面有许多分支,每个分支有许多分支......直接就爆炸了,你把每个都记忆一遍可以少算很多什么时候去用记忆化:当一个分支有许多要重复去算的节点就可以去用记忆化package love8; import java.util.Scanner; public class Main { static long [][][]memonew long[20][20][20]; public static void main(String[] args) { //这题就是典型的递归加记忆化 //所谓记忆化就是去把数据存起来,你下次去用就不用重复去算了 Scanner sc new Scanner(System.in); while (true){ long asc.nextLong(); long bsc.nextLong(); long csc.nextLong(); if(a-1b-1c-1){ break; } long r w(a,b,c); //这里有个小细节,printf是没有带换行的如果你想去换行 //1.在最后的%d后面加个\n //2.去输入一个System.out.pritnln() System.out.printf(w(%d, %d, %d) %d\n,a,b,c,r); } } public static long w(long a,long b,long c){ if(a0||b0||c0) return 1; if(a20||b20||c20) return w(20,20,20); //下面就开始去进行记忆化搜索了 if(memo[(int)a][(int)b][(int)c]!0)return memo[(int)a][(int)b][(int) c]; //它这里有个很聪明的做法,我不直接返回这个值,而是先去把这个值先去记忆化一下之后,在去返回 long res; if(abbc){ res w(a,b,c-1)w(a,b-1,c-1)-w(a,b-1,c); } else { resw(a-1,b,c)w(a-1,b-1,c)w(a-1,b,c-1)-w(a-1,b-1,c-1); } //把值取记忆化一下 memo[(int)a][(int)b][(int)c]res; return res; } }考点:dfs记忆化/普通dfs/dp核心思想:就是一个递推式子: f(n)nf(1)f(2)f(3).....f(n/2); f(6)6f(3)(3,1;3)f(2)(2,1;2)f(1)(1); 所以f(6)f(7) 因为里面有许多要重复去计算的地方去加个记忆化,加快搜索速度法一:dfs记忆化版本(无论法一,法二,方法的核心思想完全一样,都是那个递推式子)import java.util.Scanner; public class Main { static Scanner sc new Scanner(System.in); static int nsc.nextInt(); static int count 0; static int []memonew int[n5]; //这里我选择去用dfs的记忆化版本去写 public static void main(String[] args) { //核心思想:就是一个递推式子: //f(n)nf(1)f(2)f(3).....f(n/2); //f(6)6f(3)(3,1;3)f(2)(2,1;2)f(1)(1); //所以f(6)f(7) //因为里面有许多要重复去计算的地方去加个记忆化,加快搜索速度 System.out.println(dfs(n)); } public static int dfs(int n){ int sum1; //这里采用的是递归记忆化 if(memo[n]!0)return memo[n]; for(int i1;in/2;i){ sumdfs(i); } memo[n]sum; return sum; } }法二:动态规划dp版本import java.util.Scanner; public class Main { //这里我选择去用dp去写 public static void main(String[] args) { //核心思想:就是一个递推式子: //f(n)nf(1)f(2)f(3).....f(n/2); //f(6)6f(3)(3,1;3)f(2)(2,1;2)f(1)(1); //所以f(6)f(7) Scanner sc new Scanner(System.in); int nsc.nextInt(); int []fnew int[n5]; f[1]1; for(int i2;in;i){ f[i]1; for(int j1;ji/2;j){ f[i]f[j]; } } System.out.println(f[n]); } }考点:01背包/动态规划注意看复杂度,是100,如果你用dfs的01背包去写,如果超过25的是一定会超时的,所以这题只有用动态规划(dp)去写这里还是给出过了9/10个测试点的dfs代码,有个测试点超时了import java.util.Scanner; public class Main { static Scanner sc new Scanner(System.in); static int nsc.nextInt();//菜品种类 static int Msc.nextInt();//金钱 static int []arrnew int[n]; static int count0; public static void main(String[] args) { //又是典型的0-1背包问题 for (int i 0; i arr.length; i) { arr[i]sc.nextInt(); } dfs(0,0); System.out.println(count); } public static void dfs(int de,int sum){ if(den){ if(sumM){ count; } return; } //hais只用选与不选 //不选 dfs(de1,sum); //选 if(sumarr[de]M) { dfs(de 1, sum arr[de]); } } }解决do问题必要的步骤:下面是动态规划的版本,我会在代码中先去给出详解的注释import java.util.Scanner; public class Main { public static void main(String[] args) { //本题注意去看数据范围,我们知道,对于0-1背包的dfs版本来说 //时间复杂度是O(2的n次方),如果n大于25是一定会去超时的 //所以本题要想AC 必须要去用dp(动态规划版本) //dp问题解题方法: //定义状态(数组用什么)→写出状态转移→设置边界→确定顺序(循环方向,大-小/小--大)→输出答案 Scanner sc new Scanner(System.in); int n sc.nextInt();//种类数 int msc.nextInt();//钱数 int []arrnew int[n]; for (int i 0; i n; i) { arr[i]sc.nextInt(); } //一.定义状态(数组用什么) //dp[i][j] 从第 i 道菜开始包括第 i 道手里还剩 j 元时能正好花完的方案数。 int [][]dpnew int[n1][m1]; //二.写出状态转移,选与不选 //不选:dp[n][m]dp[n1][m]//n1道菜,剩下为m元钱的方案数 // 选:dp[n][m]满足可以选的情况下dp[n1][m-a[i]] //设置边界比如全部选完了,钱也全部花完了才行 dp[n][0]1; //确定循环外层是从大到小,内层是从小到大/从大到小 //因为你外层的前一个状态要用到后面的 for(int in-1;i0;i--){ for(int j0;jm;j){ //不选,剩余的钱不变 dp[i][j]dp[i1][j]; //选 if(jarr[i]){ dp[i][j]dp[i1][j-arr[i]] ; } } } System.out.println(dp[0][m]); } }知识点:dp动态规划 01背包package love8; import java.util.Scanner; public class Main { public static void main(String[] args) { //这道采药的题目,又是典型的一道01背包题目 //因为数据量是100远远大于25,要想AC只可以动态规划 //动态规划的本质:过去的最优解是未来最优解的起点。 //动态规划的本质用过去的最优解拼出未来的最优解不重复算走过的路。 Scanner sc new Scanner(System.in); int Tsc.nextInt(); int Nsc.nextInt(); int []timenew int[N1]; int []valuenew int[N1]; for (int i 1; i time.length; i) { time[i]sc.nextInt(); value[i]sc.nextInt(); } //一.定义状态 //dp[i][j] 就是去选第i各植物的时候,剩余j时间的最大值 int [][]dpnew int[N1][T1]; //二.状态转移方程 //不选第i株,那么他的价值就是上株的 //选第i株,如何让价值更大?因为假如你挖第i株假如价值接近0,然后时间还接近无穷,你的上一株 //价值接近无穷,然后时间还接近0,你还会选第i株吗?你肯定不会去选,然后去选上一株了, //但此时你还要去去想想时间,要去选,那么我现在经过的时间,一定是去大于规定的时间的,比如现在我的 //time是30秒,要去挖的规定的时间是10秒,然后我肯定可以选择去挖,但还剩下20秒,然后你肯定只有去 //上一株去挖(i-1去挖,但你也不知道我花这20秒可不可以把这个挖完,挖不完就是0,但幸运的是,在挖第去i-1) //的时候你就已经把dp[i-1][j]的所有时间确定了,然后你就可以去挖了 //以此类推,当把所有的植株跑完,时间,你就可以得到最大的值 //当然这个过程,还是要靠你自己多去感悟 //三.边界条件 //没有,因为你超过规定时间的数据我是肯定不会去记录的 //四.确定计算顺序 //经过第二步状态转移方程的分析,要去获取第i的价值,你是必须要去知道第i-1的 //所以植株循环顺序是从小到大的,然后就是去确定时间顺序,好像都行,你无论是从小到大 //还是从大到小,因为你i-1的植物全部都去去记录,然后你去i都会去调用 //五,获取答案 //完整代码演示: for(int i1;iN;i){ for(int j0;jT;j){ //不选 dp[i][j]dp[i-1][j]; //选 if(jtime[i]){ dp[i][j]Math.max(dp[i][j],dp[i-1][j-time[i]]value[i]); } } } System.out.println(dp[N][T]); } }知识点:动态规划01背包/dfs选与不选法一:动态规划:import java.util.Scanner; public class Main { public static void main(String[] args) { //注意看本题的m25的所以动态规划,或者dfs,应该都可以去solve //法一:动态规划 //动态规划的本质就是用空间去换时间 //一.定义状态:确定dp数组的含义 //dp[n][m] 表述在当前重要度的情况下,剩余钱的最大权重 //二.状态转移方程 //要么选,要么不选. //不选,钱不变,权重就是上一个的, //选就从当前选的权重和上一个权重中取个大的 //三.初始化为0 //四.是确定顺序 //外层是从小的到大的,因为你大的要去依赖大的 //内层是从没有具体顺序,因为每个钱的权重都要去算下 //五.写答案与代码 Scanner sc new Scanner(System.in); int nsc.nextInt();//钱数 int msc.nextInt();//个数 int []arrnew int[m1];//钱数 int []arr1new int[m1];//重要度 //钱数与重要度的输入 for (int i 1; i arr.length; i) { arr[i]sc.nextInt(); arr1[i]sc.nextInt(); } int [][]dpnew int[m1][n1]; for(int i1;im;i){ for(int j1;jn;j){ //不选 dp[i][j]dp[i-1][j]; //选 if(jarr[i]){ dp[i][j]Math.max(dp[i][j],(dp[i-1][j-arr[i]]arr[i]*arr1[i])); } } } System.out.println(dp[m][n]); } }法二:dfs暴力搜索:因为本题数据量少于25,用dfs可以AC你的每个物品都有2种可能是选与不选,是在同一个二叉树下,不是写成2棵二叉树,结果一颗全不选,一棵全选,这种迷之操作你自己想想可行吗?是同棵二叉树,每个分支都有选或者不选2种可能package love10; import java.util.Scanner; public class Main { static Scanner sc new Scanner(System.in); static int mosc.nextInt();//钱的总额 static int ksc.nextInt(); //有多少种 static int [] arrnew int[k];//钱 static int [] arr1new int[k];//权重 static int min0; public static void main(String[] args) { //注意看本题的m25的所以动态规划,或者dfs,应该都可以去solve //法二:dfs暴力搜索 for (int i 0; i arr.length; i) { arr[i]sc.nextInt(); arr1[i]sc.nextInt(); } dfs(0,0,0); System.out.println(min); } //反思:你是每个物品,最后都有选和不选2种情况,而不是把他们分成2棵选,不选的二叉树去写 public static void dfs(int dep,int sum,int sum1){ if(depk){ if(minsum1){ minsum1; } return; } //不选 dfs(dep1,sum,sum1); //选 if(sumarr[dep]mo) { dfs(dep 1, sum arr[dep], sum1 arr[dep] * arr1[dep]); } } }