世界网站,优化大师电脑版官方,wordpress ie9,合肥网站开发公司0. 前言 PS#xff1a;本人并不是集训队的成员#xff0c;因此代码写的烂轻点喷。。。本专题一方面是巩固自己的算法知识#xff0c;另一方面是给NBU学弟学妹们参考解题思路#xff08;切勿直接搬运抄袭提交作业#xff01;#xff01;#xff01;#xff09;最后…0. 前言 PS本人并不是集训队的成员因此代码写的烂轻点喷。。。本专题一方面是巩固自己的算法知识另一方面是给NBU学弟学妹们参考解题思路切勿直接搬运抄袭提交作业最后该系列博客AC代码均以Java语言提交C/C的可以参考思路编写代码 1. 题目详情
1.1 题目一王老师爬楼梯
1.1.1 题目信息
题目描述 王老师爬楼梯他可以每次走1级或者2级或者3级楼梯输入楼梯的级数求不同的走法数。要求递推求解如果N很大需要高精度计算。 输入要求 一个整数NN1000。 输出要求 共有多少种走法。 输入样例 10 输出样例 274 来源 NBUOJ
1.1.2 算法思路递推动态规划
本题是动态规划的入门题可以让同学较好的从递推的思维转向动态规划思维 动态规划五步走重要
状态定义这一步是相当重要的定义一个合适的状态表示是解题的关键我们假设dp[i]为走到第i级台阶的走法总数状态转移方程假设我们使用上一步骤的状态表示那么我们需要思考 dp[i] 可以由哪些状态转移得到根据题意王老师最后可以跨1步也可以跨2步也可以跨3步到达第i级台阶因此可以得出状态转移方程为dp[i] dp[i - 1] dp[i - 2] dp[i - 3](其中i 4)状态初始化由于我们在i4时直接套用该公式会造成数组越界因此我们需要初始化dp[1]、dp[2]、dp[3]的值填表顺序根据我们的状态转移方程我们发现dp[i]的值可以由前三项推出因此填表顺序是从左往右填写的返回值根据题目含义我们需要输出第n级台阶的走法个数因此我们填表完毕后需要返回的就是dp[n]
示例我们假设输入为4进行举例 即通俗来说本题的递推思路就是将王老师走到第i级台阶的最后一步的步数进行分类一共有三种情况
case1最后走了一步dp[i - 1]case2最后走了两步dp[i - 2]case3最后走了三步dp[i - 3]
1.1.3 AC代码Java实现 NBUOJ上面Java带中文注释会报错因此这里放了两个版本的代码前面不带注释的可以直接跑OJ通过后面的方便读者阅读 1.1.3.1 温馨提示
由于本题的n值最大为1000因此当n值过大时会溢出整数的表示范围无论是Java的long类型还是C的long long都不行因此本题需要借助 大数相加 的模板不过咱们Java程序员可以使用标准库提供的 BigInteger 下面简单介绍相关常用的API
API返回值说明new BigInteger(String str)BigInteger实例使用字符串表示的数值构造实例BigInteger.valueOf(long num)BigInteger实例使用long类型表示的数值构造实例x.add(BigInteger y)BigInteger实例返回x和y所表示的大数相加的结果x.multiply(BigInteger y)BigInteger实例返回x和y所表示的大数相乘的结果
1.1.3.2 不带注释版本
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();BigInteger[] dp new BigInteger[n 1];dp[1] BigInteger.valueOf(1);dp[2] BigInteger.valueOf(2);dp[3] BigInteger.valueOf(4);for (int i 4; i n; i) {dp[i] dp[i - 1].add(dp[i - 2]).add(dp[i - 3]);}System.out.println(dp[n]);}
}1.1.3.3 带注释版本
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();// 1. 状态定义dp[i]表示王老师走到第i级台阶的走法数BigInteger[] dp new BigInteger[n 1];// 2. 状态初始化dp[1] BigInteger.valueOf(1);dp[2] BigInteger.valueOf(2);dp[3] BigInteger.valueOf(4);// 3. 状态转移方程for (int i 4; i n; i) {dp[i] dp[i - 1].add(dp[i - 2]).add(dp[i - 3]);}// 4. 返回值System.out.println(dp[n]);}
}1.1.4 扩展题
这里放一些跟本题类似的OJ题读者可自行尝试解题
LeetCode70 爬楼梯https://leetcode.cn/problems/climbing-stairs/LeetCode118 斐波那契数列https://leetcode.cn/problems/pascals-triangle/
1.2 题目二铺砖
1.2.1 题目信息
题目描述 对于一个2行N列的走道。现在用12或22的砖去铺满。问有多少种不同的方式请用递推方式求解。如果N很大需要高精度计算。下图是一个2行17列的走道的某种铺法 输入要求 一个整数NN1000。 输出要求 共有多少种铺法。 输入样例 30 输出样例 715827883 来源 NBUOJ
1.2.2 算法思路递归动态规划
动态规划五步走重要
状态定义这一步是相当重要的定义一个合适的状态表示是解题的关键我们假设dp[i]表示为2行i列的砖的铺法总数状态转移方程假设我们使用上一步骤的状态表示那么我们需要思考 dp[i] 可以由哪些状态转移得到根据题意我们可以根据最后一块砖的长度为1还是为2进行区分因此可以得出状态转移方程为dp[i] dp[i - 1] 2 * dp[i - 2](其中i 3)状态初始化由于我们在i3时直接套用该公式会造成数组越界因此我们需要初始化dp[1]、dp[2]的值填表顺序根据我们的状态转移方程我们发现dp[i]的值可以由前两项推出因此填表顺序是从左往右填写的返回值根据题目含义我们需要输出长度为n的铺砖方法数因此我们填表完毕后需要返回的就是dp[n]
示例也许上面的文字描述有点抽象还是以画图进行举例 相信此图一出大家瞬间就明白公式dp[i] dp[i - 1] 2 * dp[i - 2](其中i 3)的由来了其实就是根据最后一块砖的摆法划分出不同的方案
1.2.3 AC代码Java实现 NBUOJ上面Java带中文注释会报错因此这里放了两个版本的代码前面不带注释的可以直接跑OJ通过后面的方便读者阅读 1.2.3.1 温馨提示
由于本题的n值最大为1000因此当n值过大时会溢出整数的表示范围无论是Java的long类型还是C的long long都不行因此本题需要借助 大数相加 的模板不过咱们Java程序员可以使用标准库提供的 BigInteger 下面简单介绍相关常用的API
API返回值说明new BigInteger(String str)BigInteger实例使用字符串表示的数值构造实例BigInteger.valueOf(long num)BigInteger实例使用long类型表示的数值构造实例x.add(BigInteger y)BigInteger实例返回x和y所表示的大数相加的结果x.multiply(BigInteger y)BigInteger实例返回x和y所表示的大数相乘的结果
1.2.3.2 不带注释版本
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();BigInteger[] dp new BigInteger[n 1];dp[1] new BigInteger(1);dp[2] new BigInteger(3);for (int i 3; i n; i) {dp[i] dp[i - 1].add(dp[i - 2].multiply(new BigInteger(2)));}System.out.println(dp[n]);}
}1.2.3.3 带注释版本
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();// 1. 状态定义dp[i]表示2行i列的铺法数BigInteger[] dp new BigInteger[n 1];// 2. 状态初始化dp[1] new BigInteger(1);dp[2] new BigInteger(3);// 3. 状态转移方程for (int i 3; i n; i) {dp[i] dp[i - 1].add(dp[i - 2].multiply(new BigInteger(2)));}// 4. 返回值System.out.println(dp[n]);}
}1.3 题目三整数分割(1)
1.3.1 题目信息
题目描述 N年M月O日CX和ZJS同学在刚学玩整数加减后就在那里比试谁厉害。比试内容是将一个正整数N拆成若干个正整数的和。看谁拆的多谁就赢。为了赢得比赛CX就向你求助一个整数的所有拆分方法。 输入要求 输入N 1 N 50 。 输出要求 对于N的拆分方法请以字典序排列数字越大越排前面。每一种拆分之间以一个空格分开。 输入样例 7 输出样例 来源 NBUOJ
1.3.2 算法思路暴力DFS深搜
这里直接给大家介绍我的算法思路了观察输出用例我们可以发现数字的排列顺序就是从大到小的因此我们可以从大到小不断添加元素如果target就回溯其中target的时候就进行输出这样我们就可以不重不漏的找到所有的拆分情况 算法步骤重要
我们设计一个递归函数dfs(int[] numArr, int curLen, int curSum, int target, int curNum)用于查找所有的拆分情况各个参数含义如下所示
numArr保存已经被拆分的数字curLen记录numArr的元素个数curSum当前numArr元素之和即已经拆分元素之和target拆分目标和curNum当前需要进行匹配的元素
然后从[curNum —— 1]不断从大到小尝试添加元素到拆分数组直到所有情况都搜索完毕
1.3.3 AC代码Java实现 NBUOJ上面Java带中文注释会报错因此这里放了两个版本的代码前面不带注释的可以直接跑OJ通过后面的方便读者阅读 1.3.3.1 优化点
本题如果使用Java语言是比较不容易过的我的代码做优化的地方有如下几点
输入输出优化输入流将Scanner换成了BufferReader、输出流将System.out换成了PrintWriter数据结构优化使用List集合保存拆分元素频繁调用add和remove方法开销太大因此我换用数组保存拆分元素并且由于输入组数很多打印频率非常高于是我使用StringBuildler保存全部的结果最后统一打印函数参数优化此时终于将时间变成了 2016ms最后一步优化就是将StringBuilder和numArr数组从函数参数中抽离到成员变量省去了函数调用过程中传参的开销至此程序优化到1703ms 1.3.3.2 不带注释版本
package week1.blog_code.exer1002;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;public class Main {private static int[] numArr new int[51];private static StringBuilder stringBuilder new StringBuilder();public static void main(String[] args) throws IOException {BufferedReader reader new BufferedReader(new InputStreamReader(System.in));PrintStream printStream new PrintStream(System.out);String line null;while ((line reader.readLine()) ! null) {int target Integer.parseInt(line);numArr new int[51];stringBuilder new StringBuilder();dfs(numArr, 0, 0, target, target);printStream.print(stringBuilder.toString());}}public static void dfs(int[] numArr, int curLen, int curSum, int target, int curNum) {if (curSum target) {for (int i 0; i curLen - 1; i) {stringBuilder.append(numArr[i] );}stringBuilder.append(numArr[curLen - 1] \n);return;}for (int i curNum; i 1; i--) {if (curSum i target) {numArr[curLen] i;dfs(numArr,curLen 1, curSum i, target, i);}}}
}1.3.3.3 带注释版本
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;public class Main {private static int[] numArr new int[51];private static StringBuilder stringBuilder new StringBuilder();public static void main(String[] args) throws IOException {// 缓冲输入流高级版平替scannerBufferedReader reader new BufferedReader(new InputStreamReader(System.in));// 打印流高级版平替System.out.printPrintStream printStream new PrintStream(System.out);String line null;while ((line reader.readLine()) ! null) {int target Integer.parseInt(line);numArr new int[51];stringBuilder new StringBuilder();dfs(numArr, 0, 0, target, target);printStream.print(stringBuilder.toString());}}/*** param numArr 当前拆分元素构成的数组* param curLen 当前拆分数组长度* param curSum 当前拆分方法之和* param target 目标和* param curNum 当前遍历到的数*/public static void dfs(int[] numArr, int curLen, int curSum, int target, int curNum) {// 出口当前拆分和目标和就不用继续搜索if (curSum target) {for (int i 0; i curLen - 1; i) {stringBuilder.append(numArr[i] );}stringBuilder.append(numArr[curLen - 1] \n);return;}for (int i curNum; i 1; i--) {if (curSum i target) {// 将i值加入拆分数组中numArr[curLen] i;// 继续深搜dfs(numArr,curLen 1, curSum i, target, i);}}}
}
1.3.4 扩展题
这里放一些跟本题类似的OJ题读者可自行尝试解题
LeetCode46 全排列https://leetcode.cn/problems/permutations/description/LeetCOde78 子集https://leetcode.cn/problems/subsets/description/
