题号 | 关键点 | 备注 | |
309. Best Time to Buy and Sell Stock with Cooldown | 1. 动态规划general的思想,后一个状态取决于前面的一个或者几个状态。这个题也不例外,但是induction rule不是特别明显。
2. 涉及到的状态太多,比如我是买还是卖,什么时候买卖,我当前的状态是否需要cool down之类的。用一个一维数组,if else的情况太多很难想清楚。
-> 关键点 a. 一个数组表示之前的状态太复杂,考虑开2个数组,分别记录买的时候的最大利润和卖的时候的最大利润。开2个数组来存dp的状态是很多题目通用的技巧,比如一些string的题,从左往右扫一遍,然后从右往左再扫一遍。
> 关键点b. 动态规划考虑当前问题和小1号问题之间的联系。所以buy[i]取决于buy[i - 1] 和 sell[i - 2] (因为有冷冻期)。 想清楚induction rule 当前问题和小一号问题之间的关系是整个题目的关键
| //todo: 把股票相关的问题过一遍 | | | | |
|
jump game1 && 2 | 1. 贪心法涂色是最优解法
2. 判断dp[i] 的状态的时候,需要遍历左侧所有的点,不能只从右往左找到第一个点,因为可能会漏掉最优解 | | |
221. Maximal Square | induction rule是这道题的关键:
dp[x][ y] = min(dp[x- 1][ y -1], dp[x- 1][y], dp[x][y - 1]) + 1
首先别忘了+ 1, 其次理解为什么是选三者的最小,可以自己画画图,结果是这三个正方形的overlapping的区域。 | | |
279. Perfect Squares | 关键点:
1. dp[x]的物理意义, 组成x大的数最少需要多少个square number
2. 类似于jump game: 要在dp[x] 左侧所有点都过一遍去找最小的可能的解。找到所有的而不是一个
3. for (int j = 1; i - j * j >= 0; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
} 注意理解这个循环控制条件 以及>= | | |
Search a 2D Matrix II | 关键点:
1. 还是二分法的思想,但是重点在于如何缩小搜索空间,或者说扔掉一半
2. 不是像search 2d matrix 1 一样,每次能找到个中间的点,扔掉一半,目前是从左到右,从上到下是sort的。这样的话,如果选了中间的点,无法更新搜索空间。关键点是,选取角落上的点,每次将搜索空间缩小一行或者一列。其实还是根据它sort的性质来缩小搜索空间,但是不是死板的选择一个中点来扔一半。
| //todo 明天写一遍 | |
| | | |
| | | |