Part 1 递归和递推

1. 简单斐波那契数列

n = int(input())

st = [0]*(47) # 注意这个地方，需要将数组空间设置的大一些，否则会数组越界
st[1] = 0
st[2] = 1
# 这个方法相当于是递推，即先求解一个大问题的若干个小问题
def dfs(u):
    if u ==1:
        print(st[1],end=" ")
    if u ==2:
        print(str(st[1])+" "+str(st[2]),end=" ") # 注意在这个地方，在acwing当中需要进行强制类型转换
    if u>2 :
        for i in range (3,u+1):
            st[i] =st[i-1]+st[i-2]
        for i in range (1,u+1):
            print(st[i],end=" ")
    return
dfs(n)

# 方法2 采用递归的方法，递归可以看做将一个大问题分解为若干个小问题，进行求解
def fibonacci(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        fib_list = [0, 1] # 注意这个地方，python列表的下标从0开始
        for i in range(2, n):
            fib_list.append(fib_list[i-1] + fib_list[i-2])
        return fib_list[-1]

n = int(input())
# 输出斐波那契数列的前 n 个数字
for i in range(1,n+1):
    print(fibonacci(i), end=' ')

2. 递归实现指数型枚举

# 指数枚举相当于每一个位置的数字可以选择或者不选
n = int(input())

st = [0] * (n+1) #python当中的下标是从0开始的。该数组用于保存每个位置数字的选择情况。0表示无判断，2表示不选，1表示选

def dfs(u):
    if u > n:
        for i in range(1, n + 1):
            if st[i] == 1:
                print(i, end=' ')
        print()
        return #注意，这里需要一个return

    st[u] = 2
    dfs(u + 1)      # 第一个分支：不选
    st[u] = 0       # 恢复现场

    st[u] = 1
    dfs(u + 1)      # 第二个分支：选
    st[u] = 0

dfs(1)

3. 递归实现排列型枚举

# 顺序1 依次枚举每个数放到哪个位置
# 顺序2 依次枚举每个位置放哪个数

# 相当于是在求解一个全排列问题
# 排列问题当中需要一个判断是否重复的数组

# 方法1：
n = int(input())
st = [0]*(n+1) # 表示当前的状态，0表示还没放数，1-n表示放了哪一个数
used =[False]*(n+1) # 表示某个数是否被用过, true表示已经用过

def dfs(u):
    if u>n: #边界
        for i in range (1,n+1):
            print(st[i],end=' ') #打印每一个方案
        print()
        return #注意这个return的位置
    # 依次枚举每个分支，即当前位置可以填哪些数
    for i in range (1,n+1):
        if used[i] ==False:
            st[u] =i
            used[i] =True
            dfs(u+1) # 注意每次递归运行到这里的时候现场还没有恢复
            #恢复现场
            st[u] =0
            used[i] = False

dfs(1)

4.递归实现组合型枚举

n,m = map(int,input().split())
st = [0]*30

def dfs(u,s): # u表示从第几个位置开始枚举，第二个位置表示当前从哪一个数开始
    if u ==m+1: #边界，表示已经选了m个数
        for i in range (1,m+1):
            print(st[i],end=' ')
        print()
        return
    for i in range(s,n+1):
        st[u] =i
        dfs(u+1,i+1) # 注意这个地方，u相当于是指示当前是枚举第几个位置，i相当数是指示当前位置开始可以选择的最小的数

        st[u] =0 # 恢复现场

dfs(1,1)

方法2：

n,m = map(int,input().split())
st = [0]*30

def dfs(u,s): # u表示从第几个位置开始枚举，第二个位置表示当前从哪一个数开始
    if u+n-s < m: # 剪枝，相当于想后面所有数都选上都不够m个，则无解
        return
    if u ==m+1: #边界，表示已经选了m个数
        for i in range (1,m+1):
            print(st[i],end=' ')
        print()
        return
    for i in range(s,n+1):
        st[u] =i
        dfs(u+1,i+1) # 注意这个地方，u相当于是指示当前是枚举第几个位置，i相当数是指示当前位置开始可以选择的最小的数

        st[u] =0 # 恢复现场

dfs(1,1)

5. 带分数问题

n = int(input())
st = [False] * 10
backup = [False] * 10

ans = 0


def check(a, c):
    b = n * c - a * c
    if not a or not b or not c:  # a,b,c 都不可以等于0
        return False

    backup =st[:] # python当中的切片操作

    while b: # 此处需要注意将一个数各个位上的数字取出来的方法
        x = b % 10  # 取个位 先去取个位上的数字
        b //= 10  # 个位删掉
        if not x or backup[x]: # 需要去判断x是否为0，以及这个数是否被用过
            return False
        backup[x] = True

    for i in range(1, 10): # 这个 for循环相当于去判断1-9是否都已经使用过
        if not backup[i]:
            return False

    return True


def dfs_c(u, a, c):
    global ans
    if u == n:
        return
    if check(a, c) == True:
        ans += 1
    for i in range(1, 10):  # 这部分相当于是去选c
        if st[i] == False:
            st[i] = True
            dfs_c(u + 1, a, c * 10 + i) # 注意这里再一个数字后加上一位的方法
            st[i] = False


def dfs_a(u, a):  # u相当于是当前用了几个数字,a相当于当前位置a放置的数
    if (a >= n):  # 当a>n的时候，这种情况直接舍去
        return
    dfs_c(u, a, 0)  # 相当于在a的递归搜索数的叶子节点，再依次遍历 c

    for i in range(1, 10):  # 这部分相当于去选a，即全排列位置a上的数字
        if st[i] == False:
            st[i] = True
            dfs_a(u + 1, a * 10 + i)
            st[i] = False


dfs_a(0, 0)
print(ans)