动态规划例题

设有n 种不同面值的硬币，每个硬币的面值存于数组$T[1:n]$中。现在用这些硬币来找钱。各种硬币使用的个数不限。设计一个动态规划算法以计算找出钱m 时，所用的硬币的最小个数C。

def change_money(T,m):
    T.sort()                             # 保证面额单调递增
    n=len(T)
    C=[[0]*(m+1) for i in range(n)]      # j=m时找的钱为m，因此初始化到m+1大小
    for j in range(m+1):
        if j%T[0]==0:
            C[0][j] = j//T[0]            # 边界条件，只用最小面额的硬币
        else:
            C[0][j] = float('inf')       # 最小面额硬币无法找钱时，不可能找钱
    for i in range(1,n):
        for j in range(1,m+1):
            plans = []
            for k in range(j//T[i]+1):   # k 是要用新的面额硬币的个数
                plans.append(C[i-1][j-k*T[i]]+k)   # 去掉用大额硬币的金额，剩下的金额找钱
            C[i][j]=min(plans)           # 在不同k值的方案中选最优
    return C[n-1][m]

设计一个动态规划算法从n 个数构成的数列中找出最长单调递增子序列。

def LCS(X,Y):
    # 使用最长公共子序列算法求解
    n = len(X)
    m = len(Y)
    C=[[0]*m for i in range(n)]
    B=[['']*n for i in range(n)]
    for i in range(1,n):
        for j in range(1,m):
            if X[i]==Y[j]:
                C[i][j]=C[i-1][j-1]+1
                B[i][j]="ul"
            elif C[i-1][j]>=C[i][j-1]:
                C[i][j]=C[i-1][j]
                B[i][j]="up"
            else:
                C[i][j]=C[i][j-1]
                B[i][j]="left"
    return B,C
def print_subsequence(B,X,i,j,ans):
    if i==0 or j==0:
        return
    if B[i][j]=="ul":
        print_subsequence(B,X,i-1,j-1,ans)
        ans.append(X[i])
    elif B[i][j]=="up":
        print_subsequence(B,X,i-1,j,ans)
    else:
        print_subsequence(B,X,i,j-1,ans)

def longest_subsequence(X):
    # X[0]恒为0，不表示序列元素
    B,C=LCS(X,[0]+sorted(X[1:]))
    ans=[]
    print_subsequence(B,X,len(X)-1,len(X)-1,ans)
    return ans