还是股票问题的变形。可以进行 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...

134. 加油站 如果从 i 开始 到 j 有和小于 0，则 i 和 j 中所有节点都不能作为起始点。如果整个 list 的和大于 0 那必然可以分成一部分小于 0 一部分大于 0 的两部分，也就是有解。 135. 分发糖果 先都看左边，再都看右边860.柠檬水找零 优先用 10 块的 406.根据身高重建队列 身高从大到小排序，然后考虑把小一点的数插入到大的数前面，这样不影响大数的排列（符合比大数还大的数目规则）记录一下 python insert 的语法 res.insert(people[i][1],people[i])

122.买卖股票的最佳时机II 贪心，有利润差可以赚就加入到最终的值，如果后续发现后续继续增长，继续加到利润差里面。 55. 跳跃游戏 顺序遍历数组，每次更新可以跳到的最远位置 45.跳跃游戏II 顺序遍历数组，每次更新可以跳到的最远位置。 当当前位置是上一轮跳到的最远位置，增加Step 1005.K次取反后最大化的数组和 按照 abs 排序，尽可能翻转最大的负数。 如果数组全部都变为正数则翻转 abs 最小的数

三道题目 发饼干，最长子序和，摆动序列。主要是摆动序列。 如果发现有摆动的情况直接加入即可。 如果是同向的则要更新上一次的差值，让摆动的可能性尽可能大一些。