动态规划

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？

状态： d[i] 记录钱数是i 需要的最少的硬币数

状态转移方程：d[i] = min{ d[i-m[j]]+1 } m = [1,3,5]

def get_min_num(money):
    m = [1, 3, 5]
    d = [i for i in range(money+1)]
    d[0] = 0
    for i in range(1, money+1):
        min_num = 0
        for j in range(3):
            if i-m[j] >= 0:
                d[i] = min((d[i-m[j]])+1, d[i])
    print(d)

一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度

状态：d[i] 为 以 A[i]结尾的最长非降子序列的长度

状态转移方程：d[i] = max{1, d[j]+1},其中j<i,A[j]<=A[i]

def LIS(l, n):
    d = [i for i in range(n)]
    d[0] = 1
    for i in range(1, n):
        max_dj = 1
        for j in range(i):
            if l[j] <= l[i]:
                max_dj = max(d[j]+1, max_dj)
        d[i] = max_dj
    print(d)