摘要 通过取模运算来模拟在数组中循环搜索元素，这比在数组后拼接一个相同数组更方便，空间复杂度更低。 “接雨水”和“柱状图中的最大矩形”，都可以看成是对每个柱子，找一组 3 个...
发简信
IP属地：江苏
-
代码随想录算法训练营打卡Day59&60 | LeetCode503 下一个更大元素II、LeetCode42 接雨水、LeetCode84 柱状图中最大的矩形 -
代码随想录算法训练营打卡Day58 | LeetCode739 每日温度、LeetCode496 下一个更大元素I摘要 单调栈方法的时间复杂度是O(n)，只需要一层循环遍历一次输入数组，代码更简洁，逻辑更巧妙。 栈内元素从栈顶到栈底递增（或非递减），找的是任意一个元素的右边第一个比该元素...
-
代码随想录算法训练营打卡Day57 | LeetCode647 回文子串、LeetCode516 最长回文子序列
摘要 今天的两道题目是区间 dp 的入门题目，以每一个区间作为一个状态来定义 dp 数组和递推公式。 子串（子字符串）要求元素在原序列（原字符串）中连续，子序列不要求元素在原...
-
代码随想录算法训练营打卡Day56 | LeetCode583 两个字符串的删除操作、LeetCode72 编辑距离
摘要 编辑距离问题中，插入一个字符和删除一个字符，对于使得两个字符串相等的作用是一样的，都是使得两个字符串更加接近，所以可以统一只使用“插入”或者只使用“删除” 可以进行”修...
-
代码随想录算法训练营打卡Day55 | LeetCode392 判断子序列、LeetCode115 不同的子序列摘要 套用“最长公共子序列”的思路，LeetCode392 判断子序列可以转化为：求s和t的最长公共子序列的长度，并判断这个最长公共子序列的长度是否和s的长度相等。 Leet...
-
代码随想录算法训练营打卡Day53 | LeetCode1143 最长公共子序列、LeetCode1035 不相交的线、LeetCode53 最大子数组和摘要 如果不要求子序列中的元素在原序列中连续，相比于要求“连续”，dp数组的定义和递推公式是不一样的。 如果要求“连续”，那dp数组定义为以具体的元素结尾；如果不要求连续，那...
-
代码随想录算法训练营打卡Day52 | LeetCode300 最长递增子序列、LeetCode674 最长连续递增子序列、LeetCode718 最长重复子数组摘要 如果答案在dp数组中的位置不是固定的，可以在dp数组的更新过程中记录可能的答案，简化代码，例如今天的三道题，都可以在每次更新dp数组后来记录最大值。 通过dp数组的定义...
-
代码随想录算法训练营打卡Day51 | LeetCode309 最佳买卖股票的时机含冷冻期、LeetCode714 买卖股票的最佳时机含手续费摘要 有些动态规划的题目的难点在于如何划分状态和这些状态之间如何进行转移，列出可能的状态以及转移到这些状态的可能，是定义dp数组及数组下标、推导递推公式的关键。 画出简单的状...
-
代码随想录算法训练营打卡Day50 | LeetCode123 买卖股票的最佳时机III、LeetCode188 买卖股票的最佳时机IV
摘要 只买卖一次股票，和不限制次数地买卖股票，只是在递推公式上有差别。而且，这两种情况都不需要记录完成买卖的次数。 指定了至多买k次股票，这就暗含着每天的状态信息要有买卖股票...
-
代码随想录算法训练营打卡Day49 | LeetCode121 买卖股票的最佳时机、LeetCode122 买卖股票的最佳时机II
摘要 贪心算法可以看作是动态规划的特例，可以使用贪心算法解决的问题往往都可以使用动态规划解决，而动态规划往往是解决一类问题的通法。 买卖股票的问题，通过添加一个维度来保存更详...
-
代码随想录算法训练营打卡Day48 | LeetCode198 打家劫舍、LeetCode213 打家劫舍II、LeetCode337 打家劫舍III摘要 如果一步选择会受之前的选择影响，可以考虑是否能使用动态规划。 不需要遍历环的所有可能序列，只需要从某个位置将环拆开。 树形 dp 要结合二叉树遍历和动态规划的思路，先划...
-
代码随想录算法训练营打卡Day46 | LeetCode139 单词拆分、多重背包问题摘要 如何选取物品有时也会影响代码的执行效率，虽然不同的选取物品的方法的时间复杂度可能在同一个数量级，但有时候执行效率依然有比较明显的差距。比如判断一个字符串的一个子串是否是...
-
代码随想录算法训练营打卡Day45 | LeetCode70 爬楼梯、LeetCode322 零钱兑换、LeetCode279 完全平方数
摘要 用背包问题的思路解决具体问题时，要明确什么是物品，物品的重量是什么，物品的价值是什么，以及要求的背包的状态是什么（装入的价值最大、装满背包使用的物品数最少，装满背包有多...
-
代码随想录算法训练营打卡Day44 | 完全背包问题、LeetCode518 零钱兑换II、LeetCode377 组合总和IV摘要 只需改变递推公式的一处，就可以将 0-1 背包问题变为完全背包问题。 使用滚动数组时，0-1 背包倒序遍历重量的维度，保证每件物品最多被选取一次；而完全背包正序遍历重量...
-
代码随想录算法训练营打卡Day43 | LeetCode1049 最后一块石头的重量 II、LeetCode494 目标和、LeetCode474 一和零摘要 用动态规划解决问题时，不仅要从简单的子问题来考虑递推公式，也要从问题的整体来考虑，看问题的输入参数本身有什么性质和公式，也有助于得到递推公式。 LeetCode1049...
-
代码随想录算法训练营打卡Day42 | 0-1 背包问题、LeetCode416 分割等和子集摘要 0-1 背包问题是动态规划的经典问题，通过“缩小”背包来找到问题的简单的子结构，再“放大”背包，用子结构来推导答案。 推导dp[i][j]所需的状态不一定在二维dp数组...
-
代码随想录算法训练营打卡Day41 | LeetCode343 整数拆分、LeetCode96 不同的二叉搜索树
摘要 整数拆分和不同的二叉搜索树，这两个问题，都可以看做是从整体中不断拆出子结构（整数的子结构是更小的整数，二叉树的子结构是子树），模拟拆分子结构的过程，有助于思考递推公式。...
-
代码随想录算法训练营打卡Day39 | LeetCode62 不同路径、LeetCode63 不同路径II摘要 从到达当前状态的有几种可能来思考，是一种确定dp数组及数组下标含义的方式 滚动数组是一种能够在动态规划中降低空间复杂度的方法，当我们在使用递推方程计算下一步状态的时候，...
-
代码随想录算法训练营打卡Day38 | LeetCode509 斐波那契数、LeetCode70 爬楼梯、LeetCode746 使用最小花费爬楼梯
摘要 通过简单的题目来熟悉方法论。 和贪心法只需要每一步保证局部最优相比，动态规划的下一步的决策需要根据之前的状态推导。贪心法只需要保存和局部最优相关的信息，动态规划需要保存...
-
代码随想录算法训练营打卡Day37 | LeetCode738 单调递增的数字、LeetCode968 监控二叉树摘要 不同类型的问题，即使都具有贪心选择性质，解题思路也可能差别很大，需要多看多练。 比较实用的一个办法是，从简单的问题开始模拟求解的过程，对如何形成贪心策略往往很有启发。 ...