高中信息技术之递归题解（一）
1. 爬楼梯
爬一个 n 级楼梯，他一步可以最多爬 k 级楼梯，并且他每步至少爬一级台阶（他不能爬小数级台阶，也不能往回走）。
输入两个数 n 和 k ，你需要输出 n 个数，分别表示他走 1 步爬完楼梯的方案数，走 2 步爬完楼梯的方案数，⋯，走 n 步爬完楼梯的方案数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ans = [0 for _ in range(1145)]
def solve(step, height):
if(height > n):
return
elif(height == n):
ans[step] += 1
return
else:
for i in range(1, k+1):
solve(step+1, height+i)
n, k = map(int, input().split())
solve(0, 0)
print(*ans[1:n+1])
首先确定递归函数所要包含的状态：步数和爬到了第几级。然后确定边界条件：当超过了 height 时，即为到达终点，那么给当前步数的方案数加上一。最后确定起始条件：刚开始步数为 $0$ ，也是在第 $ 0$ 个台阶。
2. 跷跷板
有 n 个人在玩翘翘板，你需要将这 n 个人分成两组，使他们的体重差最小。
2.1 常规做法
考虑到对于每个人，可以将其体重放到组A，也可以放到组B，那么我们就可以在每一个分支的时候进行两种情况的下一轮递归。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
g1 = []
g2 = []
ans = 11145141919810
def dfs(step):
global ans
if(step==n):
ans = min(ans, abs(sum(g2) - sum(g1)))
else:
g1.append(w[step])
dfs(step+1)
g1.pop(-1)
g2.append(w[step])
dfs(step+1)
g2.pop(-1)
n = int(input())
w = list(map(int, input().split(" ")))
dfs(0)
print(ans)
其中， g1 g2 为体重的列表。当步数到达 $n$ 时即为到达终点，那么计算最小体重差；否则进行枚举，若选取其到组A，就放进去；然后考虑组B，但在考虑组B前，要先清除之前的状态，我们称之为回溯，先 pop 掉之前数组里的内容，然后再进行新的枚举。
2.2 二进制枚举
对于这类 0/1 问题，我们还可以使用二进制枚举，使得空间更小且时间复杂度常数更小。
1
2
3
4
5
6
7
8
9
10
11
12
13
bi = 0
n = int(input())
a = list(map(int, input().split()))
ans = 1145141919810
while bi < (1 << (n + 1)):
su = [0, 0]
for i in range(n):
stat = 1 & (bi >> i)
su[stat] += a[i]
ans = min(abs(su[0] - su[1]), ans)
bi += 1
print(ans)
对于每一个二进制位，它表示的是组A或组B，然后进行计算。
3. 数的拆分
任何一个大于 1 的自然数 n，总可以拆分成若干个小于 n 的自然数之和。
现在给你一个自然数 n，要求你求出 n 拆分成一些数字的和的方式。
假设当前 dfs 传进来一个要拆分的数字。那么，我们可以考虑先从这个大数中分离出一个小数出来。显然，这个小数的范围为 $ 0 \sim (n-1) $ 。又因为我们需要将数字从小到大排列，那么在枚举拆出来的小数的时候，从已拆出数列表的最后一个开始枚举起即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = int(input())
arr = []
def dfs(step):
if(sum(arr)==n):
for i in range(len(arr)):
print(arr[i], end="+" if i != len(arr)-1 else "\n")
elif(sum(arr)>n):
return
else:
if(not arr):
for i in range(1, n):
arr.append(i)
dfs(step+1)
arr.pop(-1)
else:
for i in range(arr[-1], n - sum(arr) + 1):
arr.append(i)
dfs(step+1)
arr.pop(-1)
dfs(0)
4. 全排列
按照字典序从小到大输出长度为 n 的全排列。
首先生成一个从 $ 1 \sim n$ 的数列，然后新引入一个标记是否用过的数组 used ，如果已经使用过，那么在下一轮递归的时候就不考虑再使用这个数字了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
arr = []
used = [False for i in range(n+1)]
def dfs(step):
if(len(arr)==n):
print(*arr)
else:
for i in range(1, n+1):
if(not used[i]):
used[i] = True
arr.append(i)
dfs(step+1)
used[i] = False
arr.pop(-1)
dfs(0)
5. 走迷宫
斯宝走进了另一个迷宫。
这个迷宫共有 n×m 个格子，第 i 行第 j 个格子用 (i,j) 表示。
每个格子共有两个状态：
.表示这个位置是个空地，可以行走。#表示这个位置是堵墙，不能行走，也不能穿过。
斯宝每次可以从一个位置，向上下左右四个方向走一格，但是不能跃出迷宫外。具体的，如果她在 (i,j) ，那么她可以到达 **(i−1,j),(i,j−1),(i+1,j),(i,j+1**) 四个位置（如果四个位置都在迷宫内）。
斯宝一开始在 (1,1) 位置，她希望能走到 (n,m) ，可是她现在在迷宫里面，所以请求你帮助她求出任意一种，能到达 (n,m) 的方案。
如果没有可行的方案，输出 -1。
保证 (1,1) 和 (n,m) 两点为空地。
这是属于图的搜索，对于每一点，我们可以从上、下、左、右四个方向进行下一轮递归。递归时注意边界，不能越界；同时保存路径，在回溯时及时弹出旧的废弃路径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
inp = input().split()
n, m = int(inp[0]), int(inp[1])
mp = []
for i in range(n):
s = input()
mp.append([c for c in s])
# print(n, m, mp)
vis = [[False] * m for _ in range(n)]
path = []
Flag = False
def output():
print(len(path))
for i in path:
print(i[0] + 1, i[1] + 1)
def dfs(x, y):
path.append((x, y))
if x == n - 1 and y == m - 1:
Flag = True
output()
exit(0)
vis[x][y] = True
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and nx < n and ny >= 0 and ny < m and not vis [nx][ny] and mp[nx][ny] == '.':
dfs(nx, ny)
path.pop()
dfs(0, 0)
if not Flag:
print(-1)