浅析递推，递归及动态规划
概念介绍及理解
递推：从前面计算的结果推出后面的结果，数学语言描述就是从f(0),f(1)…f(n-1)可以推出f(n),所以递推公式是关键。
递归：从后往前推，以结果出发，逆推，数学语言描述就是，我要求f(n),那得先求f(n-1),要求f(n-1)那得先知道f(n-2),一直到f(1)或者f(0)是容易求的结果，然后再回推回去计算出f(n),可以看出关键点也在递推公式。
动态规划：是运筹学的一个分支，将一个复杂的问题分解成多个简单的子问题，依照同样的方式再分，直至最简化可以求解。
我暂且不从理论上来讲学，从几个实际问题来看下我是怎么运用递推或者递归来解决的。
全排列问题
问题描述：给定一个序列，如（A，B，C…）,输出这个序列的全排列的组数和序列。
问题解析：
假设有N个字符需要全排列，最简单的想法是先考虑第一个在N中选一个，然后第二个是剩下里面的N-1中选一个，依次类推，直到最后一个，所以数量就是N*（N-1）*…*1,即N！；这是数学的方法，若是让计算机照这个思路来可行吗？如果是三个字符，可以这样实现：
a=[0,1,2]#将A,B,C看成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]]#将选定的三个元素组合在一起
s.append(el)
print(s,len(s))
思路很简单，就是每层循环去除掉一个元素，然后最后将选定的元素组合；但是如果按照这个思路那如果我要排列的元素很多，那循环层数就会很多，有没有办法让循环层数减少，至少是写出来看少一点，答案是可以的，因为我们看到基本每层循环里面处理的过程都差不多，我们其实可以用递归将这个过程提取出来，下面代码这样实现的：
a=[0,1,2]
s=[]
def swap(arr,p):
#arr，需要排列的数组；p,已经选中元素的序列
if arr:
for i in arr:
temp=arr[:]
temp.remove(i)
p1=p[:]
p1.append(i)
swap(temp,p1)#temp是删除元素i后的数组，p1是选中了元素i的序列
else:
s.append(p)#arr是空说明元素已经选完
return
swap(a,[])
print(s,len(s))
问题又来了如果需要全排的数量比较大，那么通过递归栈可能会溢出，又没有通过递推的方式实现的呢，经过探索式有的，现在我们从简单的情况开始，正向来推：
1.假设有一个元素，很显然，只有一种排列方式A
2.若有两个元素，那有两种AB，BA,数学表示集合为{AB,BA},记S(2)={AB,BA}
3.三个元素有6个，ABC，ACB,BAC,BCA,CAB,CBA,记S(3)={ABC,ACB,BAC,BCA,CAB,CBA}
观察在S(2)中AB元素加上C的话有三种方法，分别为CAB,ACB,ABC;依照这个思路我们可以这样推对于S(n-1)的每个元素，当我们加入新的一个元素X的时候，那有n中插入方式。因此根据这个方式我们可以用递推方式编写代码如下：
# -*- coding=utf-8 -*-
'''
实现序列为N的全排列，将全排数组和个数输出
'''
N=3
x=[i for i in range(N)]
dps=[[] for i in range(N+1)]#用于记录从0到N的全排列序列的序列
for i in range(1,N+1):
if i==1:
dps[i]=[[0]]#一个元素时的排列
if i>1:
for arr in dps[i-1]:
for j in range(len(arr)+1):
temp=arr[:]
temp.insert(j,x[i-1])#可以有n-1个位置插入
dps[i].append(temp)#新形成的序列计入dps中
print(dps[N],len(dps[N]))
不定方程求解问题
问题描述：给定一个方程x1+x2+x3+…+xn=N,其中x1,x2…xn均为正整数，求解方程的所有解集。
问题解析：
我们先考虑三个未知数的情况，x1+x2+x3=N,显然N>=3,当N=3时只有一组解x1=1,x2=1,x3=1,记作S(3)={[1,1,1]}；当N=4时，显然在N=3的基础上某个未知数加上1就可以了，加的方式有三个，分别在x1,x2,x3上，因此S(4)={[2,1,1],[1,2,1],[1,1,2]},依次类推，所以我们以递推方式可以实现，在S(n)的解集可以在S(n-1)的解集上实现，假设S(n-1)的一组解为x1,x2…x(n-1)，那S(n)的一组解肯定是在上面解的基础上某个元素加1，按照这个思路我们可以用代码实现，如下：
# -*- coding=utf-8 -*-
'''
给定方程序列，给定和N，求解出解的方程个数，并穷举出来
'''
N=4#未知数的个数
M=6#未知数的和，方程里面的N
dps=[[] for i in range(M+1)]#存放每个和对应的解集
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#遍历的i-1的每个解的元素+1
dps[i].append(temp)#在dps[i]中加入这个解
solv(M)
print(dps[M],len(dps[M]))
分钱问题
问题描述：现有给定金额，比如有1元，3元和11元的，每个面值的右若干，给定一个金额，求最少数量可以凑出该金额的数量,并给出分配方案。
问题解析：
假设给定金额为n，凑出的币最少数量为f(n),那么如果少一张，可能就是1元的，3元的或者11元的，因此f(n)就是f(n-1),f(n-3),f(n-11)这三者的最小值再加上1，代码实现如下：
# -*- coding=utf-8 -*-
'''
现有给定金额的人民币若干，给定一个金额，求最少数量可以凑出该金额的数量,并给出分配方案。
'''
coin=[1,3,11]
N=10#给定金额
dp=[0 for i in range(N+5)]#记录每个金额的最小数量
dp[0]=0
s=[0 for i in range(N+1)]#记录每次金额增加时选择的是哪个面值
f=[0,0,0]#用于记录每个面值币的数量
def coin_solve():
for i in range(1,N+1):
num=[1000,1000,1000]
if i>=1:
num[0]=dp[i-1]#上一张面值是1
if i>=3:
num[1]=dp[i-3]#上一张面值是3
if i>=11:
num[2]=dp[i-11]#上一张面值是11
minNum=1000
index=0
#找出num中的最小值
for j,el in enumerate(num):
if el<minNum:
minNum=el
index=j
dp[i]=minNum+1
s[i]=index#记录选择的面值
coin_solve()
i=N
count=0
#在s序列中从后往前推，如最后一张是1的话，那面值照N-1的，在s序列中再找s(N-1)里面的面值，依次类推
while True:
f[s[i]]=f[s[i]]+1
i=i-coin[s[i]]
count=+1
if i<=0:
break
print(f"最小数量是：{dp[N]},每个币种数量是：{f}")
二维数组最短路径问题
问题描述：给定一个二维数组（n行，m列），以（0,0）为起点，（n-1,m-1)为终点，移动只能是向右或者向下，求他们之间的最短路径值及走法。
问题解析：
如图所示的二维数组，假设走到坐标(i,j)的最短距离为f(i,j),显然只能有两种方法到(i,j)，一种是从左边（i,j-1)来，一种是从(i-1,j)来，那只需要比较f(i,j-1),f(i-1,j)，其中较小者再加(i,j)上的值就是f(i,j)的值；再看下边界情况，在第一行中的点显然只有一种走法就是f(0,j),只能从f(0,j-1)过来；同样的第一列的f(i,0)只能从f(i-1,0)过来，按照这个思路代码实现如下：
# -*- codfing=utf-8 -*-
'''
问题：给定一个二维数组（n行，m列），[0,0]为起点，[n-1,m-1]为终点，求最短路径
'''
X=3
Y=3
arr=[[1,2,1],[3,1,2],[2,1,1]]#给定的二维数组
dp=[[0 for i in range(X)] for j in range(Y)]#用于记录到每个点的最短距离
s=[[[0,0] for i in range(X)] for j in range(Y)]#用于记录在到每个点的上一个点坐标
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]#终点就在起点
s[i][j]=[0,0]
if i==0 and j>0:
dp[i][j]=dp[0][j-1]+arr[i][j]#第一行的情况
s[i][j]=[i,j-1]
if i>0 and j==0:
dp[i][j]=dp[i-1][j]+arr[i][j]#第一列的情况
s[i][j]=[i-1,j]
if i>0 and j>0:#中间点的情况
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=[]
#从终点开始反推
while True:
point=[x,y]
line.insert(0,point)#每次从开头加
prePoint=s[point[0]][point[1]]#上一个点坐标
x=prePoint[0]
y=prePoint[1]
if x==0 and y==0:#到原点就终止
print([0,0])
break
print(f"最短路径值为：{dp[N-1][N-1]}，路径为：{line}")