从凑硬币理解动态规划

题目：
凑硬币，给出1，2，5币值大小的硬币，求最少的个数的硬币凑出n。

例子：
给出7，答案是2
给出11，答案是3

代码1:python（动态规划）

Class Solution:
	def coinCount(n):
		coins = [1, 2, 5]
		values = [0]
		for i in range(n)+1:
			//python列表生成器，用起来很方便
			values[i] = min([values[i-coin] for coin in coins if i-coin > 0])+1
		return values[n]
		

1. 拥有独立的最优子结构。
   最优子结构打个比方，求全校学生的最高分。这个时候分解一下，求每一个班级学生的的最高分，然后对每一个班级的最高分求最高分。这就是最优子结构。
   独立的最优子结构，再打一个比方，求全校学生的最高分和最低分的差距，这个时候如果求每一个班级的最高分和最低分的差，然后对每一个班级的差比较就没用了。因为班级的差跟其他班级的差是相关的，不是独立的。所以这个问题不满足独立最优子结构的。