最长公共子序列（LCS）定义 dpi 为 text1[0..i-1]和text2[0..j-1]的最大公共子序列，那么有转移方程如下：其实这个也非常的好理解，因为只有 text1[i-1] == text2[j-1] 的时候才能对答案做贡献，所以第一条方程就出来了，而第二条就是因为没有办法做贡献，只能在之前的部分中取一个最大的值。于是得到代码如下：func longestCommonSubs...
SnowKagura‘s blog
直面生活，热爱生活
我们知道 $x^y$ 其实就是 x 乘了 y 次，但是我们如何减少乘的次数来节省时间复杂度呢？其实可以让 y 每次都减半，x 基数变大即可。比如 $2^{...
每日温度这道题最难想到的就是如何利用单调栈来记录状态，需要存储的实际上就是温度单调递减的数组下标，然后当碰到温度比栈顶高的值时，就可以将单调栈内的部分弹出，两个下标的差就是对应的天数了。func dailyTemperatures(temperatures []int) []int { n := len(temperatures) res := make([]int, n) ...
分割数组的最大值这道题粗看没有任何的思路，看了题解感觉解法真的是很妙，利用二分和自定义的上下界条件等，获得了最终的答案。首先是上下界的定义，我们可以知道子...
全排列这题目也是一开始完全没有思路，不知道咋才能把全部的都输出一遍，感觉套for循环也不知道怎么写，后来看到答案直接恍然大悟，这其实是一个经典的回溯题，dfs+状态回溯即可完成。值得注意的是，通过这道题还突然意识到golang的函数传递其实是值传递，实在是太久没有看相关的文章有点忘记了，这里如果res的参数类型改成非指针，就会复制一份切片的结构体过去，一般情况下这不会引发任何问题，但是一旦进...