动态规划的三个重要概念：
【最优子结构】 【边界】 【状态转移方程】
题目：
有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
递归求解:走到第十级台阶的走法=走到第九级台阶的走法+走到第八级台阶的走法（往前递推），时间复杂度为O（2n）
状态转移方程：F（n）=F（n-1）+F（n-2）；
边界：n = 1 或 n = 2 时；
int F(int n)
{
if(n < 1)
return 0;
if(n == 1)
return 1;
if(n == 2)
return 2;
return f(n-1) + f(n-2);
}
备忘录算法：在递归的基础上相同节点用map或者hash map存储，时间复杂度为O（n）
int getClimbingWays(int n, HashMap < Integer, Integer > map)
{
if(n < 1)
return 0;
if(n == 1)
return 1;
if(n == 2)
return 2;
if(map.contains(n))
{
return map.get(n);
}
else
{
int value = getClimbingWays(n-1) + getClimbingWays(n-2);
map.put(n, value);
return value;
}
}
真正的动态规划：使F（N）自底向上的求解，这样的优点是在每一次迭代的过程中，我们只需要保留之前的两个子状态。时间复杂度为O（1）。
爬楼梯
int getClimbingWays(int n)
{
if(n < 1)
return 0;
if(n == 1)
return 1;
if(n == 2)
return 2;
int a = 1;
int b = 2;
int temp = 0;
for(int i = 3; i <= n; i++)
{
temp = a + b;
a = b;
b = temp;
}
return temp;
}
