动态规划知识点脑图整理：以捡硬币问题为例编写python代码

从数学的视角来看，动态规划是一种运筹学方法，是在多轮决策过程中的最优方法。

那么，什么是多轮决策呢？其实多轮决策的每一轮都可以看作是一个子问题。从分治法的视角来看，每个子问题必须相互独立。但在多轮决策中，这个假设显然不成立。这也是动态规划方法产生的原因之一。

动态规划是候选人参加面试的噩梦，也是面试过程中的难点。以下我根据自己的理解总结了动态规划相关的一些重要概念，便于从宏观上抽象理解这个算法。写的比较简单，如果有不清楚的地方，非常欢迎大家留言讨论。

下面举一个例子：

题目

有若干硬币排成一个序列，面值依次为[5,1,2,10,6,2]，现在规定不能捡相邻的硬币，请问如果捡硬币才能使得捡到的硬币总价值最大

思路

我们需要设计dp表来作为动态规划的数据模型，dp的值显然是硬币的总价值，表格的第一维是第几枚硬币，决策（也就是选择）有两个，第一个是选择第i-1个硬币，第2个是不选择第i-1个硬币，这样我们就可以写出状态转移方程：

dp[i] = max(dp[i-2]+row_coins[i-1],dp[i-1])

注意我们还需要定义边界条件：

dp[0] = 0
dp[1] = row_coins[0]

这样我们就可以得到如下代码求解了，注意我们还需要额外编写traceback回溯来把选择的硬币打印出来。

代码

#通过自定向上的方法来找到最优解
def bottom_up_coins(row_coins):
	dp = [None] * (len(row_coins)+1)
	dp[0] = 0
	dp[1] = row_coins[0]

	for i in range(2,len(row_coins)+1):
		dp[i] = max(dp[i-2]+row_coins[i-1],dp[i-1])

	return dp

c = [5,1,2,10,6,2]
dp = bottom_up_coins(c)

#通过对dp的回溯来反向查找被选择的硬币
def trace_back_coins(c,dp):
	select = []
	i = len(c)
	while i>=1:
		if dp[i] > dp[i-1]:
			select.append(c[i-1])
			i -= 2
		else:
			i -= 1
	return select

print(dp)
print(trace_back_coins(c,dp))

运行结果

我们看到，用这种方法，很快能求得我们在选取2/10/5这三枚硬币的时候，能得到最优的结果17.