Essentially a Young Tableau problem. Start from the right top right cell. At each step, we can either remove a row or a column.
Time: \(O(m + n)\)
Extra space: \(O(1)\)
My solution is a bit uncommon…
Pay attention to the following statement
At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.
This means the following:
Therefore, we can store the numbers in a compacted manner and then compute the product by brute-force.
Time: \(O(1)\) for add, \(O(32)\) for product
Space: \(O(add)\)
Sweep time stamp $t$ for 0 to \(10^5\), for each \(t\), we would like to
Step 2 is the greedy step. For correctness:
For implementation:
Time: \(O(n \log n)\)
Space: \(O(n)\)
Find the largest number in the array, then there’s a unique way to compute its value of the previous stage. Keep doing so until
Use a SortedList / a Max-Heap for quick indexing.
Time: \(O(n \log n \log C)\), where $C$ is the largest element in the given list.
Space: \(O(n)\)
自从更新了新的macOS到Catalina，我陆陆续续发现了一些问题。
很长一段时间，我一直把锅丢给Chrome和mac的新操作系统…
也许是歪打正着，我今天在网上闲逛有看看没有好的方案可以解决chrome狂吃cpu的问题。之后发现了一个帖子说禁用 Use hardware acceleration when available 这个选项会有一定的效果。 禁用了以后并没有发现明显的改善，但是微信以及Google Keep都可以瞬时切换了！非常神奇。。。
建议遇到过类似问题的小伙伴也试试看，希望可以解决你们的问题！
看来mac版本的微信内部是用Chrome来渲染的。
…
At that moment, Goldilocks woke up. When she saw the three bears, she leaped out of the bed, ran down the stairs, through the door, into the woods, and all the way home! And she never visited the house of the three bears ever again.
By Lionsgate
And let’s also say that change is neither good nor bad - it simply is. It can be greeted with terror or joy; a tantrum that says “I want it the way it was,” or a dance that says “Look, something new.”
LeetCode 630的加强版，我把它称为Min Cost Course Schedule。
给定$n$个course，每个course有三个属性
这里不妨假设所有的数都是正整数，并且$t_i \le n$。 现在要求一种最优的选课方式，使得总学分数最多。
首先，我们证明这个问题至少和01-背包一样难。
给定一个01-背包的问题：$n$个物体，每个物体的体积是$w_i$，价值是$v_i$。背包的总体积是$W$。
我们构造这样的一个min cost course schedule的问题实例。定义$n$个courses，每个course的完成时间记为$w_i$，获得学分数为$v_i$，所有的course的截止时间均为$W$。
很显然，后者问题的最优解直接imply前者01-背包的一个最优解。
接着我们给出一个基于DP的伪多项式解法。
我们先将所有的courses按照截止时间$d_i$从小到大排序，然后我们会有下面这个重要的（基于贪心的）结论。
Lemma
假设在某组最优解中，我们学习了课程$i_1, i_2, \dots, i_m$，这里$i_1 < i_2 < \dots < i_m$，那么也一定存在一组最优解使得我们从左到右顺次学习这些课程。
证明： 假设结论不立，那么一定会存在$i_x$和$i_y$使得我们先上$i_x$，然后紧接着就上$i_y$，但是$x > y$。
不妨假设$i_x$之前的课我们一共花了$T$的时间，于是我们一定有
(1) $T + t_{i_x} \le d_{i_x}$,
(2) $T + t_{i_x} + t_{i_y} \le d_{i_y}$,
(3) $d_{i_x} \ge d_{i_y}$ （这是因为$x > y$）.
现在我们颠倒一下$i_x$和$i_y$的学习顺序得到一组新的解（即，先学$i_y$，后学$i_x$），我们证明这组解依然是合法的，所以也是一组最优解（因为学习的课程总数并没有发生变化）。
(1) $i_y$之前和$i_x$之后的所有课程显然不会受到任何影响，所以它们一定是合法的。
(2) 考察$i_y$，我们总共花的时间是$T + t_{i_y} \le T + t_{i_x} + t_{i_y} \le d_{i_y}$，所以先上$i_y$没有问题。
(3) 然后考察$i_x$，我们总共花的时间是$T + t_{i_y} + t_{i_x} = T + t_{i_x} + t_{i_y} \le d_{i_y} \le d_{i_x}$，所以再上$i_x$也是合法的。$\Box$
有了上述Lemma，我们定义DP的状态$f[i][j]$表示：给定课程0到$i$，在累计上课时间不超过$j$的情况下，我们最多可以获得的学分数。状态转移如下：
\(f[i][j] = \left\{ \begin{array}{cl} 0 & \mbox{if } i < 0 \mbox{ or } j \le 0 \\ f[i][d_i] & \mbox{else if } j \ge d_i \\ f[i-1][j] & \mbox{else if } j < t_i \\ \max(f[i-1][j], f[i-1][j-t_i]) & \mbox{else} \end{array} \right.\).
正确性读者可以自行理解，其中最后一个转移式子用到了上述的Lemma，它保证了我们可以把这个课放在最后学习。最终答案是$f[n - 1][\min(\sum{t_i}, d_{n-1})]$。 时间复杂度是$O(\min(n^3, nd_{n-1}))$。
最后，上述的DP其实基本上和01-背包无异，也就是说这两个问题其实是等价的，同属于NP-Complete类。
给定一个有向图$G$，问至少添加几条有向边可以使得$G$强连通。
先对$G$求强连通分支，缩点，然后得到一个DAG。如果最后的DAG只有一个节点，那么答案是0，否则答案是$\max(in, out)$，这里$in$和$out$分别表示入度为0的点的总数和出度为0的点的总数。
首先$\max(in, out)$肯定是一个下界，因为至少需要这么多边才能完全消除入度为0的所有的点或者出度为0的所有的点。
接着，我们用归纳法来构造一组合理的解。 给定任意一个图$G$，求它的强连通分量并且缩点得到一个DAG，令这个DAG为$D$。我们假设$|D| \ge 2$，否则答案很显然是0。令$X$和$Y$分别表示$D$中入度和出度为0的点集。令$m = \max(|X|, |Y|)$。我们通过对$m$进行归纳，claim是存在一种添加$m$条边的解法让$G$变得强连通。
这个时候，很显然我们有$|X| = |Y| = 1$。假设$x$和$y$分别是$X$和$Y$的唯一元素，那么我们只需要添加边$(y, x)$即可。
当$m \ge 2$的时候，我们考虑2个case。
存在$x \in X$, $y \in Y$使得$D$不存在从$x$到$y$的路径。这时我们添加一条边$(y, x)$。假设添加过边的新图为$G’$，求它的强连通分支并且缩点得到一个DAG $D’$。我们可以断定$D’ = D \cup {(y, x)}$。原因很简单，如果$D$的点集在添加边$(y, x)$后发生了变化，唯一的可能是边$(y, x)$构成了环，这说明我们有$x$到$y$的路径，矛盾。
现在考虑新图$G’$和它的DAG $D’$，与$D$相比，$D’$少了一个入度为0的点，也少了一个出度为0的点，所以$m’ = m - 1$。根据归纳假设，我们需要再递归地添加$m’ - 1$条边，加上$(y, x)$本身，一共$m$条。
不存在上述的$x$和$y$，这意味着在DAG $D$中所有的$x \in X$都有到所有的$y \in Y$通路。这时我们可以随意取$D$中出度为0的点$y$和入度为0的点$x$，添加边$(y, x)$。如此重复$m$次即可。需要注意的是，如果某个时候不存在出度为0的点，那么就在$Y$中任取一点，如果不存在入度为0的点，就在$X$中任取一点。一个合理的推论是，当上述操作完成后，我们有以下两个性质：
i. 对于$X$中的任何一点$x$，存在某个$y \in Y$使得我们有边$(y, x)$。
ii. 对于$Y$中的任何一点$y$，存在某个$x \in X$使得我们有变$(y, x)$。
接下来，我们需要证明，为什么这样随意的添加边之后$D$会变得强连通（因此$G$也就强连通了）。实际上，任取$D$中的两个点$a$和$b$，首先一定存在某个$y_1 \in Y$（$y_1$可能是$a$本身），使得有$a$到$y_1$的路径。其次，根据性质(ii)，存在某个$x_1 \in X$使得我们有边$(y_1, x_1)$。再看点$b$，容易知道一定存在某个$x_2 \in X$使得$D$中存在$x_2$到$b$的路径($x_2$可能是$b$本身)。再根据性质(i)，存在某个$y_2 \in Y$使得我们有边$(y_2, x_2)$。最后，根据一开始的假设，$X$中的每个点都有到$Y$中每个点的路径，即存在$x_1$到$y_2$的路径，于是我们找到了一条通路$a \rightsquigarrow y_1 \rightarrow x_1 \rightsquigarrow y_2 \rightarrow x_2 \rightsquigarrow b$.