动态规划

动态规划的三个重要概念：

【最优子结构】 【边界】 【状态转移方程】

题目：

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。

递归求解:走到第十级台阶的走法=走到第九级台阶的走法+走到第八级台阶的走法（往前递推），时间复杂度为O（2ⁿ）
状态转移方程：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;
}