动态规划

【LeetCode 139】单词拆分题解。

【LeetCode 300】最长递增子序列题解。

【LeetCode 446】等差数列划分 II - 子序列题解。我们用一个二重循环去遍历 nums 中的所有元素对 (nums[i], nums[j])，其中 j<i。将 nums[i] 和 nums[j] 分别当作等差数列的尾项和倒数第二项，则该等差数列的公差 d=nums[i]-nums[j]。由于公差相同，我们可以将 nums[i] 加到以 nums[j] 为尾项，公差为 d 的弱等差子序列的末尾，这对应着状态转移 dp[i][d]+=dp[j][d]。同时，(nums[i], nums[j]) 这一对元素也可以当作一个弱等差子序列，故有状态转移dp[i][d]+=dp[j][d]+1

【LeetCode 368】最大整除子集题解。难点在于如何记录答案，最后把最大整除子集输出。幸运的是，题目没有限制输出的字典序，只要输出的是合理答案就可以。

【LeetCode 354】俄罗斯套娃信封问题题解。第一个难点在于如何同时控制 $w_i$ 和 $h_i$ 两个维度，很自然地想到先把一个维度排序，然后只需要考虑另一个维度最长递增子序列就行了。这时候就有第二个难点了，如果在 $w_i$ 这个维度，存在两个值相同的情况怎么处理，需要将 $w_i$ 相同的 $h_i$ 从高到低排序，这样相同 $w_i$ 的部分就不会相互影响。但是还是会TLE，具体如何请看题解。

【LeetCode 312】戳气球题解。本题的难点在于如何控制气球的相邻信息，每一次戳气球都会产生新的相邻的气球，但是很容易有一种做题的直觉，先判断一个气球，然后继续判断其左边和右边。怎么判断呢？可以倒过来看这些操作，将全过程看作是每次添加一个气球。我们定义方法 solve ，令 solve(i, j) 表示将开区间 (i, j) 内的位置全部填满气球能够得到的最多硬币数。由于是开区间，因此区间两端的气球的编号就是 i 和 j，对应着 val[i] 和 val[j]。

【LeetCode 337】打家劫舍III题解。很自然地想到是树状dp，分成两种情况，一种包含当前节点，另一种不包含。难点在于不包含的情况，不仅仅有左右孩子包含的情况，还有不包含的情况。

【LeetCode 188】买卖股票的最佳时机IV题解。本题的难点有三个方面：1️⃣关于 $in$ 和 $out$ 数组中 $j$ 的关系，在这里，买入卖出这一整套流程才算一次交易。那么，在卖出的那一刻，1次交易就完成了。那第一次买入，其实是第 0 次交易，第一次卖出，是第 1 次交易结束。2️⃣如何初始化，首先第一天只能买进，不能卖出，而且最多只能有一次交易，那么 $in[0][1…k]$ 和 $out[0][1…k]$ 如何初始化。3️⃣如何更新 $in$ 和 $out$ 数组。

【LeetCode 174】地下城游戏题解。本题的难点在于怎么处理血量增加的问题, 增加血量不能为之前的损失提供帮助，只会对后续有帮助。这意味着从王子救公主的思路想dp是困难的，但是公主救王子的思路dp很好做，从后往前推，当前如果可以治愈，那么当前的最小初始血量就是已经扣除的血量减去治疗量，注意不可以<1。 这意味着过量治疗。

【LeetCode 124】二叉树中的最大路径和题解。这题是树状dp的典型，如何在遍历树的过程中记录一些信息，是比较难的一个点。此外，这题有两个要记录的内容，一个是树（包括子树）的 根节点 或者 根节点和一个左/右节点 中的最大值，这个要一路记录上去，用 dp 记录。还有一个就是 根节点、左节点和右节点 与之前 dp 中的最大值，这个是最后的答案，用 ans 记录。我在解题的时候，总会忘记把 ans 跟自己做比较，也是以后需要注意的一个点。