算法练习（更新中...）

1 动态规划算法

算法简介

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

算法举例

力扣爬楼梯问题

class Solution {
    public int climbStairs(int n) {
        //else return climbStairs(n-1)+climbStairs(n-2);超时了
        //动态规划
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
    }

开始使用递归发现超时，递推公式为climbStairs(n-1)+climbStairs(n-2)，后面优化之后只需要存储前2个数值大小即可。