这次主要入门一下动态规划

Climbing Stairs

最简单的类型,因为自己对动态规划一窍不通所以学一下。

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?

\begin{aligned} f(1) &= 1\\ f(0) &= 1\\ f(n) &= f(n-1)+f(n-2) \end{aligned}

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())


这篇就到这里吧,都太简单了,熟悉一下概念,晚上做难一点的