115.不同的子序列 如果当前 s 和 t遍历的索引分别是i和 j，如果 i 和 j 不相同，则子序列个数是 dp[i-1][j] 因为求得是完整的 t 序列在 s 中的出现个数。如果 i 和 j 相同，则子序列的个数就是dp[i-1][j-1]+dp[i-1][j] 应该是t[:j-1]在s[:i-1]的个数和t[:j]在s[:i-1]出现的个数之和。需要注意的是初始化的过程。 整体遍历顺序是从上到下。所以需要初始化第一行。 同时注意 i-1的范围，所以要初始化第一列。首先是 dp[0][0] 两个空字符串，应该相等。所以初始化为 1第一列表示的是空字符在 s 中出现的个数。 s 中没有任何...

今天主要是最长公共子序列 和 判断子序列这两类问题的区分。在公共子序列问题中有不相等的时候 dp[i][j]=max(dp[i-1][j],dp[i][j-1])和子系列不相等的时候却是 dp[i][j] = dp[i][j-1] 因为判断子系列问题是给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 实际上我们转换的问题是s 字符串在在 t 字符串中最长距离。 因此不相等的时候要保持 s 字符串的完整在公共子序列问题中我们求得是 s 和 t 中最大的公共长度，无法确保当前是 s 保持完整还是 t 保持完整才能求得最终的最大公共长度。

300.最长递增子序列 首先是动态规划的方法 if nums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1) 每遍历一个 i 的时候就需要遍历前面的所有num，来更新最长的长度。复杂度是O^2 然后是 DAG 的算法， 求最长递增子序列的过程可以看做是这样的图 426783一个注意点就是，我们维持一个当前最小的子序列，如果后续有比它还小的树，则需要更新当前最小的子序列，在图中的例子就是已经有 4 了 同时要更新一个 2，尽管 4 的子序列长度可能会比 2 更长，但后续可能存在多个比 2 大数字最终导致 2 的子序列更长。然后在更新 2 的过程我...

还是股票问题的变形。可以进行 k次第k 次买入的时候考虑 k-1次卖出含冷冻期买入的时候可以考虑从冷冻期买入含交易费我的做法是买入的时候就算上手续费，然后和之前差不多

简答来说 当前第 i 天获取的利润可以对应 n 种装填还没买允许第一次买允许第一次卖允许第二次买允许第二次卖...例如第二次买 可以通过第一次卖的最大 profit 来获取当前可以买入的最低值。 而在初始化的过程中，实际上我们将第二次买和第二次卖的最低值等同于第一次买和第一次卖。 实际上允许第二次的结果是包含第一次的。

三道小偷的题目。基础的题目主要就是当前节点保存两个状态f偷与f不偷。 不偷的话就是和前面偷情况下相等。 偷的话就是max（前不偷+curval,前偷） 值得注意的就是 虽然当前状态是偷的，但不一定是真的偷了当前节点。然后就是环形题目，分成两种情况考虑就可以最后是树状dp 可以用后序遍历求解。 或者用BFS换成数组形式，然后逆推即可。 dp[parentId][0]= dp[2*parentId][1]+dp[2*parentId+1][1]+node[parentId].val dp[parentId][1]= max(dp[2*parentId][0],...[1])+max(dp[2*pa...

今天这类问题可以说是 再空间和的情况下，最大空间可以放的最少的物品数量。（目前遇到的背包问题可以求解四种问题最大值，最大数量,最小数量和方案数) 322. 零钱兑换 凑成总金额所需的 最少的硬币个数。 无所谓组合还是排序。 然后转移方程是min ，注意初始化的时候要取极大值。 279.完全平方数 同零钱兑换，就是所占的空间要手动计算一下。139.单词拆分 这个拆分获得的结果是一个排序的问题。 所以先遍历space再遍历单词 关于多重背包这里的实现是遍历所有的物品。 但是不重新调整数组，而是自己分配物品的index。 先得到一个前缀和，然后根据每次的index获取对应的weight和va...

昨天的01 背包求解的是三类问题，在空间和为space的限制下求求放入物品的最大的价值求装满背包的方法数量求背包最大可以放的物品数量01背包的一维空间遍历顺序必须是从大到小。 否则这一轮的便利结果会覆盖上一轮的。在从大到小的便利顺序要求下，必须是遍历物品类型在外，空间在内。 否则dp[s-space[i]]的结果恒为初始值，是没有更新到的。完全背包要求可以多次放入物品，此时空间遍历是要从小到大的。因为需要考虑同一个物品放多次的情况。既然是从小到大的空间顺序，就可以先遍历空间再遍历物品了。此时要区分的是两种遍历内外顺序的区别。先遍历物品种类，再遍历空间。 此时物品种类是有序的，所以遍历的方...

今天三道题目，可以说分别是背包问题的不同变形三个模型已知每个物品的重量和价值。背包空间大小为Space，求放入物品的最大的价值。变形一 在和的上限不超过 half 的情况下的最大和。已知每个物品的重量和价值。背包空间大小为Space，求装满背包的方法数量已知每个物品的重量和价值。背包空间大小为Space，求背包最大可以放的数量。最后一块石头的重量 这题实际上求得是 在和的上限不超过 half 的情况下的最大和。基础背包模型求得是 空间和上限不超过 half 的情况下的最大价值和。观察可以发现，如果将重量和价值相等的话，我们可以得到一个化简的式子也就是题目所有的内容。转换成代码就是这样目标和这题...

二维数组从 A-Z进行遍历，dp 表示 前 x 个字母的最大存储的值dp [B][space] = max(dp[A][space],dp[A][space-Bspace]+valueB)一维空间对于 space的遍历是不能从小到大的如果是从小到大的，则相同的元素可能会被放入两次在 space 遍历顺序是从大到小的情况下，必须先进行种类的遍历再进行空间的遍历如果先进行空间的遍历，则所有dp[A][space-Bspace]都是 0。 是无法分解为最小子问题的这里的最小子问题就是 space-BSpace能够放的最大的值，但是由于我们是从大到小遍历的，这个小问题是没有求解的。******可以理解...

62.不同路径 63. 不同路径 II 这两题主要是初始化的工作，第一列和第一行初始化为 1 ，如果有障碍物则后面的都为 0343.  整数拆分dp 的三种情况 dp[n] = dp[n-i]*i (n-i)*i last_I_Result96. 不同的二叉搜索树假设有i个节点，左侧有 left 个，则此时的二叉搜索树的数量可以表示为 count[left]*count[i-left-1] 这个是可以分解为子问题来解决的，

刚开始的动规几道题基本都是爬楼梯的变形。 *****************这题主要问题的到达的是下标为 n 的位置而不是n-1，所以列 dp 的时候空间要给大一下。然后既然到 fib 数了就复习一下尾递归的知识.常规递归的过程是：每次函数调用时需要记录当前函数上下文的信息，包括传入参数、局部变量值等，并将这些信息保存在栈空间（也称调用栈或运行时栈）中。举个例子来说。- 当一个函数 fib 返回值是 fib(n-1)+fib(n-2)时，函数结束前需要执行相加的操作，所以编译器不会丢弃掉这些信息。- 而如果返回值是fib(n-1,ret2,ret1+ret2)就不用保存原函数的信息，就可以减少...

今天感觉状态不对，做了挺久的。 三道题 摄像头，递增的数字和合并区间合并区间和之前的重复区间类似，不过删除变成了合并，手动维护一个当前的 end 就可以。递增数字做的很复杂，翻译成数组，一旦发现有后比前大的数字就往前遍历到时候有相同的数字。摄像头这个看了题解分成三种情况。 有 camera，被检测和不被检测。做的时候想着是用和 camera 的距离来写，但是这样空节点就不知道应该怎么处理了。

终于到了重叠区间的部分，这部分我记得之前笔试的时候做到过，不过有些变形没做出来。看了下题解，看上去是之前的做法弄错了理解不对。 我是按照 star 和 end 进行了一个排序，实际上根据贪心直接根据前面进行排序就可以了，end 的部分可以手动维护一个有序的数列452. 用最少数量的箭引爆气球每次更新最短的 end 边界 if points[i-1][1]<points[i][0]: count+=1 else: points[i][1]=min(points[i][1],points[i-1][1]) 435. 无重叠区间 if intervals[i-1][1]<=in...