这次主要入门一下动态规划。
Climbing Stairs
最简单的类型，因为自己对动态规划一窍不通所以学一下。
\[\begin{aligned} f(1) &= 1\\ f(0) &= 1\\ f(n) &= f(n-1)+f(n-2) \end{aligned}\]You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Unique Binary Search Trees
求二叉搜索树可能的种数。
\[\begin{aligned} f(1) &= 1\\ f(0) &= 1\\ f(2) &= 2\\ f(n) &= \sum_{i=1}^{n}{f(i-1) \cdot f(n-i)} \end{aligned}\]这时候发现做算法题的时候还是不需要开 vector，初始化什么的很麻烦诶，array 一个大数组就够了。
Maximum Subarray
《编程珠玑》8.4 节上有。
这是连续子向量最大和问题，所以用扫描线算法。维护历史最大向量和 以及 以当前元素为结尾的正向量和，并且不断比较更新。
仔细想想，这确实也是动态规划。
唯一要注意的是，编程珠玑里面记载的代码，似乎遗漏了全是负数序列的情况。所以如果结果为 0，要返回 *max_element(nums.begin(), nums.end())。
这篇就到这里吧，都太简单了，熟悉一下概念，晚上做难一点的