动态规划

1，什么是动态规划

私以为，动态规划就是在递归思想的基础上，用空间换时间，将已经计算过的结果用存储起来，消除冗余计算，提高算法效率。

2，什么时候使用动态规划

抽象一点来说，当一个问题可以被分为若干个规模更小的子问题，并且子问题中存在很多重复时，可以使用动态规划。

具体来说，以下几种问题可以考虑动态规划：

1. 计数问题
   • 有多少种方法从网格的左下角走到右下角
   • 有多少种方法选出k个数使其和为sum
2. 求最大最小值
   • 从网格左上角走到右下角路径的最大数字和
   • 最长上升子序列长度
3. 求存在性
   • 取石子游戏，先手是否必胜
   • 能不能选出k个数使得和是sum

3，动态规划解题步骤

1. 确定状态
   • 确定最后一步
   • 化为子问题
2. 写出转移方程(第一步做完转移方程就自然写出来了)
3. 确定初始条件(初始条件即为转移方程求不出来，但是又要用到的条件)

现在让我们来实践一下：

例题：
现在有数量不限的2元，5元，7元硬币，要求使用最少数量的硬币拼成27元。

解：
0，该题是求最少数量硬币的组合，因此使用动态规划
1，确定状态
1.1，确定最后一步，设f(x)为拼成x元需要的最少硬币数量
最后一枚硬币可以为2元，5元，7元，因此f(27)可以分别为：f(25)+1,f(22)+1,f(20)+1。
由于所求的是最少数量，因此f(27)=min{f(25)+1,f(22)+1,f(20)+1}。
1.2，化为子问题
子问题即为：要求使用最少数量的硬币拼成i元。
因此f(i)=min{f(i-2)+1,f(i-5)+1,f(i-7)+1}
2，写出状态转移方程
即为上述方程
3，确定初始条件
当i=0时，即0元可以由0枚硬币组成。
当i<0时，此时无法组成这个数量，即令f(i)=无穷

def coinChange():
    target = []
    target[0] = 0
    for i in range(27):
        target[i] = min(fun(i-7),fun(i-5),fun(i-2))+1;
    return target[27]
def fun(i,target):(用来在i<0时返回无穷)
	if i < 0:
        return Integer.Max
    else:
        return target