Concept introduction and understanding
Recurrence: deduce the following results from the previous calculation results. Mathematical language description can deduce f(n) from f(0),f(1)... f(n-1), so recurrence formula is the key.
Recursion: push forward from the back, start with the result, and push backward. The mathematical language description is that if I ask f(n), I have to find f(n-1) first. If I ask f(n-1), I have to know f(n-2) first until f(1) or f(0) is an easy result, and then push back to calculate f(n). It can be seen that the key point is also the recursive formula.
Dynamic programming: it is a branch of operations research, which decomposes a complex problem into multiple simple subproblems and divides them in the same way until it can be solved in the simplest way.
For the time being, I will not give a lecture in theory. From several practical problems, I will see how I use recursion or recursion to solve them.
Total permutation problem
Problem Description: given A sequence, such as (A, B, C...), output the number of fully arranged groups and sequences of this sequence.
Problem analysis:
Assuming that there are N characters that need to be arranged in full, the simplest idea is to consider first selecting one from N, then selecting one from the remaining N-1, and so on until the last one, so the quantity is N * (N-1) *... * 1, that is, N!; This is a mathematical method. Is it feasible to let the computer follow this idea? If it is three characters, it can be realized as follows:
a=[0,1,2]#Consider a, B and C as 0,1,2
s=[]
for i in a:
temp1=a[:]
temp1.remove(i)
for j in temp1:
temp2=temp1[:]
temp2.remove(j)
el=[i,j,temp2[0]]#Group the three selected elements together
s.append(el)
print(s,len(s))
The idea is very simple, that is, one element is removed from each layer, and then the selected elements are combined at last; But if I follow this idea, if I have a lot of elements to arrange, there will be a lot of cycle layers. Is there any way to reduce the number of cycle layers, at least write it down a little less? The answer is OK, because we see that the processing process in each layer of the cycle is not much different. In fact, we can extract this process by recursion, The following code is implemented as follows:
a=[0,1,2]
s=[]
def swap(arr,p):
#arr, array to be arranged; p. Sequence of selected elements
if arr:
for i in arr:
temp=arr[:]
temp.remove(i)
p1=p[:]
p1.append(i)
swap(temp,p1)#temp is the array after element i is deleted, and p1 is the sequence with element i selected
else:
s.append(p)#arr is empty, indicating that the element has been selected
return
swap(a,[])
print(s,len(s))
The problem comes again. If the number of full rows is relatively large, the recursive stack may overflow, but it is not realized by recursion. After exploration, let's start with a simple case and push forward:
1. Suppose there is one element. Obviously, there is only one arrangement A
2. If there are two elements, there are two kinds of AB and BA. The mathematical representation set is {AB,BA}, and the record S(2)={AB,BA}
3. There are 6 of the three elements, ABC, ACB,BAC,BCA,CAB,CBA, S(3)={ABC,ACB,BAC,BCA,CAB,CBA}
Observe that in S(2), there are three methods for AB element plus C: cab, ACB and ABC; According to this idea, we can push that for each element of S(n-1), when we add a new element X, there is an insertion mode in n. Therefore, according to this method, we can write code recursively as follows:
# -*- coding=utf-8 -*-
'''
For implementation sequence N The full array and number of the full array are output
'''
N=3
x=[i for i in range(N)]
dps=[[] for i in range(N+1)]#A sequence used to record a fully arranged sequence from 0 to N
for i in range(1,N+1):
if i==1:
dps[i]=[[0]]#Arrangement of one element
if i>1:
for arr in dps[i-1]:
for j in range(len(arr)+1):
temp=arr[:]
temp.insert(j,x[i-1])#There can be n-1 positions to insert
dps[i].append(temp)#The newly formed sequence is included in dps
print(dps[N],len(dps[N]))
Indefinite equation solving problem
Problem Description: given an equation x1+x2+x3 +... + xn=N, where x1,x2... Xn are positive integers, solve all solution sets of the equation.
Problem analysis:
Let's first consider the case of three unknowns, x1+x2+x3=N, obviously n > = 3. When N=3, there is only one set of solutions x1=1,x2=1,x3=1, written as S(3)={[1,1,1]}; When N=4, it is obvious that an unknown number can be added with 1 on the basis of N=3. There are three ways of adding, which are x1,x2 and X3 respectively. Therefore, S(4)={[2,1,1],[1,2,1],[1,1,2]}, and so on. Therefore, we can realize it in a recursive way. The solution set of S(n) can be realized on the solution set of S(n-1). Suppose that a group of solutions of S(n-1) are x1,x2... x(n-1), A set of solutions of S(n) must be an element plus 1 based on the above solution. According to this idea, we can implement it in code, as follows:
# -*- coding=utf-8 -*-
'''
Given equation sequence, given sum N，Solve the number of equations and enumerate them
'''
N=4#Number of unknowns
M=6#The sum of unknowns, N in the equation
dps=[[] for i in range(M+1)]#Store each and the corresponding solution set
def solv(n):
for i in range(1,n+1):
if i==N:
dps[i]=[[1 for x in range(N)]]
if i>N:
for arr in dps[i-1]:
for j,el in enumerate(arr):
temp=arr[:]
temp[j]=arr[j]+1#Element + 1 of each solution of traversal i-1
dps[i].append(temp)#Add this solution to dps[i]
solv(M)
print(dps[M],len(dps[M]))
Money problem
Problem Description: there are currently given amounts, such as 1 yuan, 3 yuan and 11 yuan. How many to the right of each face value? Given an amount, find the minimum quantity to get the quantity of the amount, and give the distribution scheme.
Problem analysis:
Assuming that the given amount is n and the minimum number of coins is f(n), if there is one less, it may be 1 yuan, 3 yuan or 11 yuan. Therefore, f(n) is the minimum value of F (n-1), f (n-3) and f (N-11) plus 1. The code is as follows:
# -*- coding=utf-8 -*-
'''
There are several RMB with a given amount. Given an amount, the quantity of the amount can be rounded up by finding the minimum quantity,The distribution scheme is given.
'''
coin=[1,3,11]
N=10#Given amount
dp=[0 for i in range(N+5)]#Record the minimum quantity of each amount
dp[0]=0
s=[0 for i in range(N+1)]#Record which face value is selected each time the amount increases
f=[0,0,0]#Used to record the amount of each denomination
def coin_solve():
for i in range(1,N+1):
num=[1000,1000,1000]
if i>=1:
num[0]=dp[i-1]#The previous one had a face value of 1
if i>=3:
num[1]=dp[i-3]#The previous one had a face value of 3
if i>=11:
num[2]=dp[i-11]#The previous one had a face value of 11
minNum=1000
index=0
#Find the minimum value in num
for j,el in enumerate(num):
if el<minNum:
minNum=el
index=j
dp[i]=minNum+1
s[i]=index#Record the face value of the selection
coin_solve()
i=N
count=0
#Push forward from the back in the s sequence. If the last one is 1, the face value is N-1. Find the face value in s(N-1) in the s sequence, and so on
while True:
f[s[i]]=f[s[i]]+1
i=i-coin[s[i]]
count=+1
if i<=0:
break
print(f"The minimum quantity is:{dp[N]},The quantity of each currency is:{f}")
Two dimensional array shortest path problem
Problem Description: given a two-dimensional array (n rows, m columns), with (0,0) as the starting point and (n-1,m-1) as the end point, the movement can only be right or down, and find the shortest path value and walking method between them.
Problem analysis:
For the two-dimensional array shown in the figure, assuming that the shortest distance to the coordinate (i,j) is f(i,j), it is obvious that there can only be two methods to get to (i,j). One is from the left (i,j-1) and the other is from (i-1,j). Only compare f (i,j-1) and f (i-1,j). The smaller value plus (i,j) is the value of f(i,j); If you look at the boundary, there is obviously only one way for the point in the first line, that is, f(0,j), which can only come from f(0,j-1); Similarly, f(i,0) in the first column can only come from f(i-1,0). According to this idea, the code is as follows:
# -*- codfing=utf-8 -*-
'''
Problem: given a two-dimensional array( n that 's ok, m Column),[0,0]As the starting point,[n-1,m-1]For the end point, find the shortest path
'''
X=3
Y=3
arr=[[1,2,1],[3,1,2],[2,1,1]]#Given two-dimensional array
dp=[[0 for i in range(X)] for j in range(Y)]#Used to record the shortest distance to each point
s=[[[0,0] for i in range(X)] for j in range(Y)]#Used to record the coordinates of the last point to each point
print(s)
def find_path():
for i in range(X):
for j in range(Y):
if i==0 and j==0:
dp[i][j]=arr[i][j]#The end is at the beginning
s[i][j]=[0,0]
if i==0 and j>0:
dp[i][j]=dp[0][j-1]+arr[i][j]#The first line
s[i][j]=[i,j-1]
if i>0 and j==0:
dp[i][j]=dp[i-1][j]+arr[i][j]#The first column
s[i][j]=[i-1,j]
if i>0 and j>0:#Intermediate point
if dp[i-1][j]<dp[i][j-1]:
dp[i][j]=dp[i-1][j]+arr[i][j]
s[i][j]=[i-1,j]
else:
dp[i][j]=dp[i][j-1]+arr[i][j]
s[i][j]=[i,j-1]
find_path()
N=3
x=N-1
y=N-1
line=[]
#Push back from the end
while True:
point=[x,y]
line.insert(0,point)#Add from the beginning every time
prePoint=s[point[0]][point[1]]#Previous point coordinates
x=prePoint[0]
y=prePoint[1]
if x==0 and y==0:#Terminate at the origin
print([0,0])
break
print(f"The shortest path value is:{dp[N-1][N-1]}，The path is:{line}")