浅析递推,递归及动态规划

浅析递推,递归及动态规划

概念介绍及理解

递推:从前面计算的结果推出后面的结果,数学语言描述就是从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}")
上一篇:1220:单词接龙(感觉挺难的!!)


下一篇:下载npm依赖包报错 npm ERR code ERR_TLS_CERT_ALTNAME_INVALID npm ERR errno ERR_TLS_CERT_ALTNAME_INVALID