不得不说，刷题已经和爬山、溜娃一样，成为湾区三俗，基本几个湾区的工程师碰在一起，讨论的话题总跳不出这个圈。爬山，哦不，刷题作为一个贯穿码农整个职业生涯的必须品（就算是我目前呆的微国外服务器软谷歌这种养老公司也总得跳一跳，毕竟雪花的大包裹是真香啊），几年来基本每天不间断的刷，算是对这一块略有心得。帖子的前半部分想分享一些我作为面试官的常出的一些经典题目，以及题目思路的解析以及一些同类题的归纳，帖子的后半部分我会参考坛友们的留言和拍砖，来决定后面的走向

帖子会长期保持更新，只要是带娃的间隙就会偷偷上来更一下，尽量保持每周两更。

由于太多人加我 VX，我也创建了一个算法工作交流群，大家感兴趣可以加我拉你进群

我的 VX：sxxzs3998 不管是具体的题目讨论还是给帖子的建议和拍砖，或者想进群都欢迎添加（记得加我要备注 v2 ）
第一周（题目一）

有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1 或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。求所能获得硬币的最大数量。

第一周（题目一）
解题思路
我们来看一个区间，这个区间的气球长这样
（蓝、绿、红、粉、黄）
i j
假设这个区间是个开区间，最左边索引 i，最右边索引 j
我这里说 “开区间” 的意思是，我们只能戳爆 i 和 j 之间的气球，i 和 j 不要戳
 DP 思路是这样的，就先别管前面是怎么戳的，你只要管这个区间最后一个被戳破的是哪个气球
这最后一个被戳爆的气球就是 k
假设最后一个被戳爆的气球是粉色的，k 就是粉色气球的索引
然后由于 k 是最后一个被戳爆的，所以它被戳爆之前的场景是什么样子？
（蓝、 、 、粉、黄）
i j
是这样子的朋友们！因为是最后一个被戳爆的，所以它周边没有球了！没有球了！只有这个开区间首尾的 i 和 j 了！！
这就是为什么 DP 的状态转移方程是只和 i 和 j 位置的数字有关
假设 dp[i][j] 表示开区间 (i,j) 内你能拿到的最多金币
那么这个情况下
你在 (i,j) 开区间得到的金币可以由 dp[i][k] 和 dp[k][j] 进行转移
如果你此刻选择戳爆气球 k，那么你得到的金币数量就是：
total=dp[i][k]+val[i] * val[k] * val[j]+dp[k][j]
注：val[i] 表示 i 位置气球的数字
然后 (i,k) 和 (k,j) 也都是开区间
那你可能又想问了，戳爆粉色气球我能获得 val[i]*val[k]*val[j] 这么多金币我能理解(因为戳爆 k 的时候只剩下这三个气球了)，
但为什么前后只要加上 dp[i][k] 和 dp[k][j] 的值就行了呀？
因为 k 是最后一个被戳爆的，所以 (i,j) 区间中 k 两边的东西必然是先各自被戳爆了的，左右两边互不干扰，大家可以细品一下
这就是为什么我们 DP 时要看 “最后一个被戳爆的” 气球，这就是为了让左右两边互不干扰，这大概就是一种分治的思想叭
所以你把 (i,k) 开区间所有气球戳爆，然后把戳爆这些气球的所有金币都收入囊中，金币数量记录在 dp[i][k]
同理，(k,j) 开区间你也已经都戳爆了，钱也拿了，记录在 dp[k][j]
所以你把这些之前已经拿到的钱 dp[i][k]+dp[k][j] 收着，
再加上新赚的钱 val[i]*val[k]*val[j] 不就得到你现在戳爆气球 k 一共手上能拿多少钱了吗
而你在 (i,j) 开区间可以选的 k 是有多个的，见一开头的图，除了粉色之外，你还可以戳绿色和红色
所以你枚举一下这几个 k，从中选择使得 total 值最大的即可用来更新 dp[i][j]
 
然后呢，你就从 (i,j) 开区间只有三个数字的时候开始计算，储存每个小区间可以得到金币的最大值
然后慢慢扩展到更大的区间，利用小区间里已经算好的数字来算更大的区间
就可以啦！

第一周（题目二）
给你一个二维整数数组 envelopes，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里。请计算 最多能有多少个 信封能组成一组这样的信封（即可以把一个信封放到另一个信封里面）。注意：不允许旋转信封。

1，动态规划解决
其实就是求最长递增子序列的一个变种，先把信封按照宽度进行非降序排序，如果宽度一样，在按照高度进行降序排序，然后再求数组高度的最长递增子序列即可。

2，把上升子序列加入到集合中（二分法查找）
我们每次遍历的时候都会拿当前值 nums[i]和 list 的最后一个元素比较如果 nums[i]比 list 最后一个元素大，说明 nums[i]加入到 list 的末尾可以构成一个更长的上升子序列，我们就把 nums[i]加入到 list 的末尾。如果 nums[i]不大于 list 的最后一个元素，说明 nums[i]和 list 不能构成一个更长的上升子序列，但我们可以用 nums[i]把 list 中第一个大于他的给替换掉。我们要保证 list 中元素不变的情况下，值越小越好，这样当我们加入一个新值的时候，构成上升子序列的可能性就越大。