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

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?

Unique Binary Search Trees

求二叉搜索树可能的种数。

这时候发现做算法题的时候还是不需要开 vector,初始化什么的很麻烦诶,array 一个大数组就够了。

Maximum Subarray

《编程珠玑》8.4 节上有。

连续子向量最大和问题,用扫描线算法,维护一个历史最大向量和,与,以当前元素为结尾向量和,并且不断比较更新。

仔细想想这确实是动态规划。

唯一要注意的是编程珠玑遗漏了全是负数序列的情况,所以如果结果为 0,要返回 *max_element(nums.begin(), nums.end())


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