不知道大家有没有一种感觉，一旦提到动态规划头就会隐隐作痛，因为动态规划这个东西一旦想清楚就十分简单，想不清楚就巨难，所以一些面试的时候，一旦被问到这样的问题就会惊出一身冷汗。今天咱们就介绍几个动态规划的问题。
括号匹配
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
当 n=3的时候，输出是这个样子的
out=["((()))","(()())","(())()","()(())","()()()"]
其实提议还是不比较好理解的，就是如果给你n对括号，那么有多少中组合的方式呢？
如果没有思路，我们就将所有的可能结果都写出来看看，看看之前的关系，从而能够帮助我们写出转移方程。
dq[0] = [""]
dq[1] = [()]
dq[2] = [()(),(())]
dq[3] = [((())),(()()),(())(),()(()),()()()]
我们观察一下看看有怎么样的规律呢?
dq[0]没什么可说的就是初始定义，dq[1]如何用dq[0]表示呢？ 似乎应该是如下表示方法
(dq[0]),这个新的最外层的括号就是我们新加入的一个括号。是不是最终的转移方程呢？ 先看看在说
比较麻烦的是dq[2]怎么表示呢？ 我们看看如下的表达方式吧
dq[2]=(dq[1])+dq[0] =(())
dq[2]=(dq[0])+dq[1] = ()()
看起来是不是有点意思啦，不要高兴的太早咱们还是要看下dq[3]的。
dq[3]=(dq[2])+dq[0]=(()()) / ((()))
dq[3]=(dq[1])+dq[1]=(())() / ()(())
dq[3]=(dq[0])+dq[2]=()()()
这个时候是不是已经清晰了呢？
$$
dq[n]=dq[a]+dq[b] \\
a+b=n-1
$$
上面的公式就是转移方程，对于动态规划的方式一定是一个小问题逐渐合并成一个大问题的解，所以以后遇到类似的问题不妨写出来各个解真实值，然后使用小规模解表示大规模解找到规律似乎就能够解答这类问题，下面就直接上代码啦。
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
if n == 0:
return []
dq = list()
dq.append(" ")
for i in range(1, n + 1, 1):
tmp = list()
for j in range(0, i):
part_0 = dq[j]
part_1 = dq[i-j-1]
for item in part_0:
for itm in part_1:
val = "(" + item + ")" + itm
val = val.replace(" ", "")
tmp.append(val)
dq.append(tmp)
return dq[n]
s = Solution()
print(s.generateParenthesis(3))
找零钱问题
有面值分别是1元，3元和5元的钱币，需要凑齐n元最少需要多少钱币呢？这就是经典的破零钱问题。
下面我就按照动态规划的思想来思考这个问题。
动态规划三要素
最优子结构
所谓最优子结构就是如何描述当前当前的最优解，一般我们通过枚举归纳来获取最优子结构。
如果想凑成0元钱币，使用$d(0)=0$
如果想凑成1元钱币，使用$d(1)=d(0)+0$
如果想凑成2元钱币，使用$d(2)=d(1)+1$
如果想凑成3元钱币，使用$d(3)=min\{d(2)+1, d(3-3=0)+1\}$
...
通过上面的归纳总结，我们发现最优子结构$d(i)=min\{d(i-1)+1, d(i-v_{j}+1)\}$就是$d(i)$, 这里的$d(i-v_{j})$表示枚举所有可能的情况，当然需要满足$i-v_{j}>=0$。
边界条件
动态规划的边界条件一般就如递归的算法出口，从上面的枚举看，当时就是$d(0)=0$
状态转移公式
状态转移就是如上面枚举归纳总结的过程，在什么状态下需要引入更多的判断，和最优子结构一样，状态转移公式就是
$$
d(i)=min\{d(i-1)+1, d(i-v_{j})+1\}
$$
实操练习
def dp(n):
scheme = [0 for x in range(n)]
money = [1, 3, 5]
for i in range(1, n):
scheme[i] = scheme[i - 1] + 1
for idx, num in enumerate(money):
if num > i:
break
if scheme[i - num] < scheme[i - 1]: # 状态转移
scheme[i] = scheme[i - num] + 1
return scheme[n - 1]
n = 10
print(dp(n + 1))
对应上面的结构看我们的实现过程，把我们的归纳过程记录到scheme中，然后每次计算新的最优结构的时候，都参照之前的最优结构，就得到了最优的解。