动态规划步骤

使用拼硬币的案例：
面值为2元、5元、7元的3种类型硬币，最少可以使用多少枚硬币拼出27元钱？

步骤1：确定状态

确定 f(x) 是什么；
f(x) = 拼出x元钱最少使用硬币数。

步骤2：转移方程

对于任意x，转移方程为：

f(x) = min{ f(x-2)+1 , f(x-5)+1 , f(x-7)+1 }

步骤3：初始条件和边界情况

边界情况：
f(-2)=f(-1)=正无穷，因为无法拼出-1或者-2元钱；

同样的，
f(1) = min{ f(-1)+1 , f(-4)+1 , f(-6)+1 }，也是正无穷，表示拼不出1元钱；

初始条件：
f(2)=1，因为用1枚2元硬币可以拼出2元；
同时，f(2) = min {f(0)+1, f(-3)+1 , f(-5)+1 },因为f负数是正无穷，
所以，
f(0)=0;

步骤4：计算顺序

一般从小到大，先计算f[0]，然后f(1)、f(2)、、、

f(负数)=正无穷；
f(0)=0;
f(1)=正无穷；
f(2)=1;
f(3)=min{f(1)+1, f(-2)+1, f(-4)+1} = 正无穷；
f(4)=min{f(2)+1, f(-1)+1, f(-3)+1} = 2；
f(5)=min{f(3)+1, f(0)+1, f(-2)+1} = 1;
、
、