动态规划

Python 77 2017-09-24 08:31

动态规划,就是找问题子问题,并且建立关系,如何找出有用的子问题,很关键

1、1,3,5面值硬币,求n元,至少需要几枚硬币组合,比如100元,

  • 如果当前1元,99元至少需要多少

  • 如果当前3元,97元至少需要多少

  • 如果当前5元,95元至少需要多少
    只要求出三种情况,最小即为所求,递推关系

      d[i] = min(d[i-1]+1, d[i-3]+1, d[i-5]+1), i >= 5
    
def coin(coins, n):
    # 假设i元需要j枚硬币d[i]=j,d[0]=0,d[1]=1
    # d[i]=min{d[i-1]+1,d[i-3]+1,d[i-5]+1}
    d = [0]*(n+1)
    d[1] = 1
    d[0] = 0
    for i in range(1,n+1):
        if i < 3:
            d[i]=d[i-1]+1
        elif i >=3 and i < 5:
            d[i] = min(d[i-1]+1, d[i-3]+1)
        else:
            d[i] = min(d[i-1]+1, d[i-3]+1, d[i-5]+1)
    return d
coins = [1,3,5]
n = 100
print coin(coins, n)

2、最大非降子序列长度

  • 以a(j)为结尾的非降子序列长度为d[j]
  • 这样序列中以每个元素结尾的长度d[j],j = 0,1,2,...
  • d[j+1] = max{ d[i]+1,if a[j+1]>=a[i],i <j+1}
  • max{d}就是最大非降子序列的长度
def longestchildes(A):
    # d[i]表示前i+1 个元素以A[i]结尾的最大非降子序列长度
    # d[1]=1
    # 如果A[2]>=A[1], d[2]=d[1]+1,否则d[2]=1
    # if A[3]>=A[2],A[3]>=A[1],d[2]=max{d[1]+1,d[2]+1}
    # A[i]与前面进行比较,求的最大值
    d = [1]*len(numbers)
    n = len(numbers)
    for i in range(n):
        for j in range(i):
            if A[i] >= A[j]:
                d[i]=max(d[i],d[j]+1)
    print d
numbers = [2,1,3,4,3.5,3.6]
longestchildes(numbers)

3、ZigZag
求数列正负相隔最大子序列,如果1,7, 4, 9, 2, 5,1>7<4>9<2>5
本身就满足,这个和上题类似,也是以numbers[i]结尾的正负相隔最大子序列为dp[i][],这里要记录当前节点是正,还是负,这样后一个节点才好与之比较

def nepo(numbers):
    lens = len(numbers)
    dp = [[1,1] for i in range(lens)]
    dp[0] = [1,1]
    i = 0

    while i < lens:
        j = 0
        while j < i:
            if numbers[i] > numbers[j]:
                dp[i][0] = max(dp[i][0], dp[j][1]+1)
            if numbers[i] < numbers[j]:
                dp[i][1] = max(dp[i][1], dp[j][0]+1)
            j += 1
        i += 1
    return dp

4、 BadNeighbors
求不相邻子序列最大和,首尾算是相邻的两个数
这个题要注意dp[i][]表示donations[i]最大不相邻子序列最大和,包含首个数,和不包含首个数最大和,

def badNeighbors(donations):
    lens = len(donations)
    dp = [0]*lens
    i = 0
    if lens == 0:
        return 0
    if lens == 1:
        return donations[0]
    if lens == 2 or lens == 3:
        return max(donations)

    dp = [[0 for i in range(2)] for i in range(lens)]
    dp[0] = [donations[0],0]
    dp[1] = [0,donations[1]]
    i = 2
    while i < lens:
        j = 0
        while j < i-1:
            dp[i][0] = max(dp[j][0]+donations[i], dp[i][0])
            dp[i][1] = max(dp[j][1]+donations[i], dp[i][1])
            j += 1
        i += 1
    return dp

5、平面上有N*M 个格子,每个格子中放着一定数量的苹果。你送左上角的格子开始,每一步只能向下或是向右走,每次走到一个格子上就把格子里的苹果收集起来,这样下去,你最多能收集到多少个苹果。
看一个简单例子,左边是原来图,右面是向下或向右两种行动方式能获得最大苹果数,换一种说法每一个格子只能从左面或上面获得苹果,要使本格子苹果最多,只能选择Max{左,上}的苹果

动态规划-JEESNS
import numpy as np
# 递归
def get_most_apples_by_recursion(apples, M, N):
    # M 行,N列
    if M == 0 and N == 0:
        return apples[0][0]
    if N == 0:
        return get_most_apples_by_recursion(apple,M-1, N) + apples[M][N]
    if M == 0:
        return get_most_apples_by_recursion(apples, M, N-1)+apples[M][N]
    return max(get_most_apples_by_recursion(apples, M, N-1), get_most_apples_by_recursion(apples, M-1, N))+apples[M][N]
# 迭代
def get_most_apples_by_iteration(apples, M, N):
    # j 行 i 列
    for i in range(N):
        for j in range(M):
            if j > 0 and i > 0:
                apples[j][i] += max(apples[j-1][i], apples[j][i-1])
            elif j > 0 and i == 0:
                apples[j][i] += apples[j-1][i]
            elif i > 0 and j == 0:
                apples[j][i] += apples[j][i-1]
apple = [[5,2,4,6], [3,7,8,2], [9,3,5,7], [1,4,3,8]]

# M 行, N列
M = len(apple)
N = len(apple[0])
A = [[0 for i in range(N)] for i in range(M)]
get_most_apples_by_iteration(apple, M, N)
print apple
文章评论