前言
相信这个故事,朋友们应该都不陌生,
从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?「从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?『从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?……』」
递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。上面的故事就是一个简单的递归,当然还有斐波那契数列等等,一系列我们熟知的。
递归
递归是将原问题拆成多个子问题然后求解,递归的代码往往很短,可能进行重复求解某些问题,而动态规划是在递归的基础上保存了子问题的解,避免重复计算。
下面我们通过例题来加深对递归的理解
斐波那契数列问题的递归
爬楼梯问题力扣
题目描述: 有 N 阶楼梯,每次可以上一阶或者两阶,求有多少种上楼梯的方法。
定义一个数组 dp 存储上楼梯的方法数(为了方便讨论,数组下标从 1 开始),dp[i] 表示走到第 i 个楼梯的方法数目。第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达,走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。
思路一:直接递归
class Solution {
public int climbStairs(int n) {
if(n == 1)
return 1;
if(n == 2)
return 2;
return climbStairs(n-1) + climbStairs(n-2);
}
}
发现超时了,原因是我们对于climbStairs递归
进行了重复的计算,dp的方程不难看出:
思路二:动态规划
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
递归实现排列型枚举
题目描述:把 1∼n 这 n个整数排成一行后随机打乱顺序,输出所有可能的次序。
输入格式:一个整数 n。
输出格式:按照从小到大的顺序输出所有方案,每行 1 个。首先,同一行相邻两个数用一个空格隔开。其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。
数据范围:1≤n≤9
输入样例:3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
思路:数据范围是1~9,推断可能选择的算法为,暴力递归,指数级别,dfs+剪枝
排列型枚举,依次枚举每个数放到哪个位置,从小到大枚举,肯定是字典序最小,转换为递归搜索树为:
import java.util.Scanner;
/**
* @Author 秋名山码神
* @Date 2023/1/30
* @Description
*/
public class 排列枚举每个数 {
static int N = 10;
static int n;
static int[] state = new int[N];//0表示没放数,1~n表示放了哪个数
static boolean[] used = new boolean[N];
public static void dfs(int u){
if(u>n){
for(int i = 1; i<=n; i++){
System.out.print(state[i]);
}
System.out.println();
return;
}
//依次枚举每个分支
for(int i = 1; i<=n; i++){
if(!used[i]){
state[u] = i;
used[i] = true;
dfs(u+1);
//恢复现场
state[u] = 0;
used[i] = false;
}
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
dfs(1);//从1开始,最后打印除了就是字典序最小
}
}
递归实现组合型枚举
题目描述:
从 1~n 这 n 个整数中随机选出 m 个,输出所有可能的选择方案。
输入格式:
两个整数 n,m ,在同一行用空格隔开。
输出格式:
按照从小到大的顺序输出所有方案,每行1个。
首先,同一行内的数升序排列,相邻两个数用一个空格隔开。
其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面(例如1 3 5 7排在1 3 6 8前面)。
数据范围:n>0,0≤m≤n ,n+(n−m)≤25
输入样例:
5 3
输出样例:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
思路:
import java.util.Scanner;
/**
* @Author 秋名山码神
* @Date 2023/1/30
* @Description
*/
public class 组合枚举每个数 {
static int N = 30;
static int n,m;
static int[] ways = new int[N];
public static void dfs(int u,int start){
//剪枝, 如果把后面的数都选上还不够m,意味这无解,例如4开始,……
if(u+n - start <m) return;
if(u == m +1){
for(int i = 1; i<=m; i++){
System.out.print(ways[i] + " ");
}
System.out.println();
}
for(int i = start; i<=n; i++){
ways[u] = i;
dfs(u+1,i+1);
ways[u] = 0;//实际上是没有意义的,恢复现场,前面给覆盖掉了
}
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
m = cin.nextInt();
dfs(1,1);
}
}
递推
前面的递归我们是从原问题来推出子问题,递推刚好相反,递推:子问题推出原问题
递推的斐波那契
题目描述:
输入一个整数N,输出这个序列的前N项。(序列为斐波那契数列)
数据范围:0<N<46
import java.util.Scanner;
/**
* @Author 秋名山码神
* @Date 2023/1/31
* @Description
*/
public class fib {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] f = new int[46];
f[1] = 0;
f[2] = 1;
for(int i = 3; i<= n; i++){
f[i] = f[i-1] + f[i-2];
}
for(int i = 1; i<=n; i++)
System.out.print(f[i]+" ");
System.out.println();
}
}
带分数
来源:第四届蓝桥杯省赛C++B/C组,第四届蓝桥杯省赛JAVAA/B组
数据范围:1 <= N < 10^6
目标是找到三个数,使得n=a+b/c,可以考虑使用暴力解法将1~9的全排列给一个个搜出来,然后每次找到一种排列,就利用二重循环将该段排列分成三段,第一段得到a,第二段得到b,第三段得到c,然后进行判断即可
优化: n是已知的,可以把等式变形为,cn = c *a + b,枚举ac,直接算出b
package 递归;
import java.util.Scanner;
/**
* @Author 秋名山码神
* @Date 2023/1/31
* @Description
*/
public class 带分数真题 {
static boolean[] st = new boolean[12];
static int[] ans = new int[12];
static int n = 100;
static int res = 0;
public static void dfs(int x)
{
if(x > 9)
{
for(int i = 1;i <= 7;i++)
for(int j = i + 1;j <= 8;j++)
{
int a = 0;
int b = 0;
int c = 0;
int cnt = 1;
for(int k = 1;k <= i;k++)
{
a += ans[k] * cnt;
cnt *= 10;
}
cnt = 1;
for(int k = i + 1;k <= j;k++)
{
b += ans[k] * cnt;
cnt *= 10;
}
cnt = 1;
for(int k = j + 1;k <= 9;k++)
{
c += ans[k] * cnt;
cnt *= 10;
}
if(b % c == 0)
{
if(a + b/c == n) {res ++;}
}
}
return;
}
for(int i = 1;i <= 9;i++)
{
if(st[i]) continue;
ans[x] = i;
st[i] = true;
dfs(x + 1);
st[i] = false;
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
dfs(1);
System.out.println(res);
}
}
翻硬币
来源:第四届蓝桥杯省赛C++B组
数据范围:n<100
暴力递归可以写
import java.util.Scanner;
/**
* @Author 秋名山码神
* @Date 2023/1/31
* @Description
*/
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String ss1 = sc.next();
String ss2 = sc.next();
char[] s1 = ss1.toCharArray();
char[] s2 = ss2.toCharArray();
int cnt = 0;
for(int i = 0; i < s1.length-1; i++){
if(s1[i] != s2[i]){
cnt++;
if(s1[i] == '*')
s1[i] = 'o';
else
s1[i] = '*';
if(s1[i+1] == '*')
s1[i+1] = 'o';
else
s1[i+1] = '*';
}
}
System.out.println(cnt);
}
}
最后
看在博主这么努力,熬夜肝的情况下,给个免费的三连吧!