思想：拆分子问题，记住过往，减少重复计算。

典型特征：
最优子结构、状态转移方程、边界、重叠子问题
eg：
f(n-1)和f(n-2) 称为 f(n) 的最优子结构
f(n)= f（n-1）+f（n-2）就称为状态转移方程
f(1) = 1, f(2) = 2 就是边界
比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重叠子问题。

解题思路：
穷举分析
确定边界
找出规律，确定最优子结构
写出状态转移方程

1.穷举分析
拆分子问题：通过固定的方法如何得到目标
eg：
当台阶数是1的时候，有一种跳法，f（1） =1
当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即f(2) = 2;
当台阶是3级时，想跳到第3级台阶，要么是先跳到第2级，然后再跳1级台阶上去，要么是先跳到第 1级，然后一次迈 2 级台阶上去。所以f(3) = f(2) + f(1) =3
当台阶是4级时，想跳到第3级台阶，要么是先跳到第3级，然后再跳1级台阶上去，要么是先跳到第 2级，然后一次迈 2 级台阶上去。所以f(4) = f(3) + f(2) =5
当台阶是5级时……

2.确定边界
当台阶数是1的时候或者2的时候，可以明确知道青蛙跳法。f（1） =1，f(2) = 2，当台阶n>=3时，已经呈现出规律f(3) = f(2) + f(1) =3，因此f（1） =1，f(2) = 2就是青蛙跳阶的边界。

3.找规律，确定最优子结构
n>=3时，已经呈现出规律 f(n) = f(n-1) + f(n-2) ，因此，f(n-1)和f(n-2) 称为 f(n) 的最优子结构。

4.写出状态转移方程
f(n) = 1;n = 1
f(n) = 2;n = 2
f(n) = f(n - 1)f(n - 2); n >= 3