这两道题虽然粗看感觉挺简单的，但是需要考虑到的东西比较多，比如如果用dfs，需要通过记忆之前计算的答案进行剪枝，否则时间复杂度是指数级别，会导致超时，用动态规划的话反而简单许多。最小路径和dfs做法如下func minPathSum(grid [][]int) int { n := len(grid) m := len(grid[0]) memo := make([]...
SnowKagura‘s blog
直面生活，热爱生活
最长公共子序列（LCS）定义 dpi 为 text1[0..i-1]和text2[0..j-1]的最大公共子序列，那么有转移方程如下：其实这个也非常的好理...
我们知道 $x^y$ 其实就是 x 乘了 y 次，但是我们如何减少乘的次数来节省时间复杂度呢？其实可以让 y 每次都减半，x 基数变大即可。比如 $2^{32}=4^{16}=16^8=256^{4}=...$这样实际上就减少了很多次乘法，从原先的 $y$ 次变成了 $log2y$ 次乘法这其实就是快速幂的思想，可以应用在单个实数乃至矩阵乘法上。将这个思路化作代码就如同下面这样：for y ...
每日温度这道题最难想到的就是如何利用单调栈来记录状态，需要存储的实际上就是温度单调递减的数组下标，然后当碰到温度比栈顶高的值时，就可以将单调栈内的部分弹出...
分割数组的最大值这道题粗看没有任何的思路，看了题解感觉解法真的是很妙，利用二分和自定义的上下界条件等，获得了最终的答案。首先是上下界的定义，我们可以知道子数组各自的和的最小值是单个元素，也就是分割的数组个数等于数组长度，而最大值就是不分割的和。于是 lo = max(nums)，hi = sum(nums)然后在这个界限中，可以利用二分找到 k 个子数组各自和最大值的最小，我们可以计算让每个...