动态规划刷题集python代码

1 爬楼梯（Fibonacci）

#有一楼梯共M级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

def fun(m):

    c = [0]*m

    c[0] = 1

    c[1] = 2

    for i in range(2,m):

        c[i] = c[i-1]+c[i-2]

    return c[m-1]

print(fun(3))

2最长公共子序列长度

def lcs(x,y,m,n):

    c = [[0]*(n+1)]*(m+1)

    print(len(c),len(c[0]))

    for i in range(m):

        for j in range(n):

            if x[i]==y[j]:

                c[i+1][j+1]=c[i][j]+1

            else:

                c[i+1][j+1]=max(c[i+1][j],c[i][j+1])

    return c[m][n]

x = [1,3,2,5,6]

y = [6,3,2,4,5,7,6]

m,n = 5,7

print(lcs(x,y,m,n))

　　变形有最短编辑距离

3 最长上升子序列长度

def lis(x,m):

    if m == 0:

        return 0

    c = [1]*m #c[i]为以i下标为结尾的最长上升子序列长度，如果m不为0，那么结果至少为1

    for i in range(m):

        for j in range(i):

            if x[i]>x[j]:

                c[i] = max(c[j]+1,c[i])

    return max(c)

x = [2,1,5,7,10,4]

m = 6

print(lis(x,m))

4 硬币找零之最少硬币方案

def coinfun(coin,aim):

    max_value = aim+1

    c = [0]+[max_value]*aim

    #两行写法，很python

    # for i in range(1,aim+1):

    #     c[i] = min([c[i-j] if i-j>=0 else max_value for j in coin ])+1

    #常规写法

    for i in range(1,aim+1):

        for j in coin:

            if i-j>=0:

                c[i] = min(c[i],c[i-j]+1)

    if c[aim] == aim+1:

        return -1 #没法找

    return c[aim]

coin = [5,2,3]

aim = 20

print(coinfun(coin,aim))

5 硬币找零之最大找零种数

def coinfun(coin,aim):

    c = [0]*(aim+1)

    c[0]=1

    for j in coin:

        for i in range(1,aim+1):

            if i-j>=0:

                c[i] += c[i-j]

    if c[aim] == 0:

        return -1 #没法找

    return c[aim]

coin = [5,2,3]

aim = 20

print(coinfun(coin,aim))

6 最大连续子序列和

#最大连续子序列和

def maxsub(A):

    dp = [0] *len(A) #以i下表为结尾的最大连续子序列和（大概这个意思，不太准确明白就行）

    dp[0] = A[0]

    for i,item in enumerate(A):

        dp[i] = item+dp[i-1] if dp[i-1]>0 else item

    return max(dp)

A = [3,-1,5,-7,4]

print(maxsub(A))

7 不相邻元素最大累加和

#最大不相邻累加和

def sum1(arr):

    c = [0]*len(arr)

    c[0] = arr[0]

    c[1] = max(arr[0],arr[1])

    for i in range(2,len(arr)):

        c[i] = max(c[i-1],c[i-2]+arr[i])

    return c[-1]

arr = [3, 2, 1, 9, 4, 2]

print(sum1(arr))