动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划

动态规划算法通常基于一个递推公式和n个初始状态。当前子问题的解将由前子问题的解推出。使用动态规划来解题只需要多项式时间复杂度。

基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。与分治法类似，基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将结果记录下来，方便之后使用。这就是动态规划法的基本思路。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。

适用条件

最优化原理（最优子结构性质）

最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

无后效性

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

子问题的重叠性

动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

经典问题

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

我们最先想到的算法一般是贪婪算法，每次减去能够减掉的最大数值，最后得出结果。

当然这在上面问题这种问题上是成立的，因为有面值是基数1元，这显然不能代表普遍性。当提供的面值是2、3、5时，要求x=11，我们发现直接粗暴地套用贪婪原理并不奏效，x-5-5=1，此时无法进行下一步，需要提供回溯。

所以说，在有些时候这类问题可以通过贪婪算法解决，但是大部分情况，我们无法直接获得想要的结果。

很明显，这个问题可以分解为:

求解凑齐x-1数值的硬币枚数+1

求解凑齐x-3数值的硬币枚数+1

求解凑齐x-5数值的硬币枚数+1

最终的结果就是这三种情况的最小值，而这三种情况又可以继续分别分解。解决的路径跟递归很相似，但是相当容易套圈~

所以我们开始尝试顺人类认知的从小数值递推到x.

现在我们在开始看上一部分DP适用条件

最优化原理
无后效性
子问题的重叠性

第一个条件显而易见的符合，第二个条件，当我们求出x-1、x-3、x-5这些结果之后，这些步骤的最终结果只是为了能够得到x的最优解，求解之后跟x+1、x+3后续再无瓜葛，这就符合了无后效性。第三个条件，从我开始分解这道问题的时候就能够得出结论。

解决

术语介绍

按照DP的知识，有下面几个重要的术语：

阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的
状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。
决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合
策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。
状态转移方程：给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k))与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律，也就是状态转移方程。

状态

上面在Encyclopedia上提到的解读可能比较抽象，状态就是问题分解得到子问题的当前解。

具体到这个例子，就是当x=[0、1、2、3、4、5、6、7、8、9、...x-1、x]这些问题的解。

我们通过基础的数据结构数组S表示子问题解，也就是原来问题的状态。

s[0]

求解需要多少枚硬币可以凑齐0元，显然，s[0]=0

s[1]

需要多少枚硬币可以凑齐1元，s[1]=1，需要1枚1元硬币

s[2]

需要多少枚硬币可以凑齐2元，s[2]=s[2-1]+1=s[1]+1=2。需要上面子问题状态再加上1枚1元硬币

s[3]

需要多少枚硬币可以凑齐3元，此时的情况就比较复杂了。我们有两种选择，当然是基于原来的状态求出。

以s[2]的状态基础在加一枚1元硬币。s[3]=s[3-1]+1
以s[0]的状态再加一枚3元硬币。s[3]=s[3-3]+1

现在的问题就是如何确定所有选择。从前面的疾苦==记录可以看出，我都是有意识的在下标上做文章，故意将s[0]===s[3-3]，这就是关键。每次我们获取当前状态，不是要从紧邻的上一个状态递推，而是根据提供给我们的硬币数值得到可能凑到当前数值的情况。

2元再加一枚1元硬币是如此，0元再加一枚3元硬币也是如此。当要求解s[5]的时候情况更加多变。候选变成了[s[4]+1,s[2]+1,s[0]+1]。每个子问题的求解都要尝试可能的求解路径状态。

4+1是一种情况，2+3、0+5是另外的情况。

那么s[3]的结果是哪一个呢，根据问题需要求解最小的硬币枚数，显然结果是Min(s[2]+1,s[0]+1)，是s[3]=1，需要1枚三元硬币

s[4]

需要多少枚硬币可以凑齐4元，s[4]=Min(s[3]+1,s[1]+1)，s[4]=2,需要一枚3元硬币的基础上再加一枚1元硬币。

上面在s[3]的求解过程中，实际上已经脱出了该问题的状态转移方程。

s[x]=Min(s[x-j]+1)，其中j是提供的硬币面值。

实现

x=input('plz input the value of x')
s=np.arange(int(x))
x_coins=(1,3,5)
for item in range(1,x-1):
	for i in x_coins:
		if item>=i and s[item-i]+1<s[item]:
			s[item]=s[item-i]+1
print(s)