动态规划
2017-09-15 本文已影响153人
阿发贝塔伽马
动态规划，就是找问题子问题，并且建立关系,如何找出有用的子问题，很关键
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 get_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}
# coins 是正整数数组，n也为正整数
coins.sort()
c_max = coins[-1]
c_min = coins[0]
d = [0]*(max(n, c_max)+1)
# 如果n在coins d[n] = 1
if n in coins:
return 1
# 对d赋初值
for el in coins:
d[el] = 1
# 递推求d[n]
# 从1开始到n
for N in range(1, n+1):
# 如果，则需要计算d[N]
if d[N] == 0:
# N 可以写成比N-{coins},最小的
d[N] = amount
for coin in coins:
if N > coin:
if d[N-coin] !=0:
d[N] = min(d[N], 1+d[N-coin])
else:
break
return d[n]
coins = [186,419,83,408]
n = 6489
print get_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{左，上}的苹果
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
-
Can I Win给定一堆数比如1到max,目标数desir,甲乙两人从堆中任意抽取数字（不能放回），当甲乙抽出数字总和大于等于desir,则最后一方获胜，现在问给出max与desir,判断甲能不能获胜。如果总和小于desir甲乙都不能获胜。
第一步：一堆数中最大的数大于等于desir，则甲选取该数，甲获胜，否则甲选取数A，desir = desir-A
第二步：如果最大数大于desir,乙获胜，否则，乙选取数B，desir = desir-B
问题可以总结为 question(numbers,desir)，每一步都可以化为这样的问题，desir在不断变小
def question(nums,desir):
