所有代码详见：https://github.com/jingminglake/Leetcode

总体思路

动态规划适合求解的问题类型是最值类型，也就是求所有解决方案中最优的，例如最大值，最小值，最好方案情况，方案个数。

• 求方案个数

求解有多少个解的问题，一般是使用自上而下的方法，也就是，先拆解成可以递归解决的子问题，

然后递归返回到上一步时候，记录其中的最优答案。

使用记忆化搜索，基于已经解决的子问题来一步步推导。

• 求最值

例如，求最大子数组大小。突破思维局限，可以宏观看问题，分为以最后一个值为结尾的情况和不以最后一个值为结尾的情况，然后，从大小为1的数组开始往后推算，得出答案。

例如，最长回文串大小。可以采用二维子问题的方法，也就是将问题变成二维的公式，然后根据公式确定二维的双重循环计算顺序（方法是看公式中是如何依赖前面信息）。

• 状态定义的方向：以 i 结尾，还是以 i 起头

二维 dp 的常用技巧是「以某某坐标为结束的子问题」，一维同理，dp[i] 默认指「以 i 结尾」或「前 i 个」。这是默认套路，但不是唯一选择，有一类题必须反过来定义成「从 i 出发」。

判据是：当「当前决策是否合法／有多好」取决于后面还没走的部分时，就必须从后往前定义。

本篇里的例子：

• 174. Dungeon Game 是最纯粹的例证。血量不能低于 1 这个约束是「未来的」——能不能活取决于后面还要掉多少血，从起点往终点推时这个信息根本不存在。所以状态必须定义成「从 i,j 出发到终点所需的最少初始血量」，自下而上、从右至左扫，答案在 dp[0][0]。
• 139. Word Break 两个方向都成立：dp[i] 表示「0 到 i 的串能否切分」是以 i 结尾；top-down 那种「dp[j] 表示 j 到 N 的串」就是以 j 起头。同一道题的两种定义并排，是最好的对照样本。
• 区间型 dp（5、516 等）dp[i][j] 表示下标 i 到 j 这一段，是「两端都定死」的第三类。循环顺序仍受同一条规律支配：格子依赖左边和下边，所以 i 从大到小、j 从小到大。

• 树形 dp 的「从 i 起头」就是「以 i 为根的子树」，编码上就是从叶子往 root 算。

• 状态定义的粒度：一个位置维护几个量

上一节讲的是状态定义的方向（朝前还是朝后），这一节讲另一个轴：一个位置上要维护几个量、各是什么含义。两个轴合起来才算把状态定义讲全。

套路只有三种：

53 一道题里同时出现了 ① 和 ②（方法三是 ①，方法二的 f／g 是 ②），是最好的对照样本。

怎么选：看转移需要「前一个位置的什么信息」

只需要「前一个位置的全局最优」   → 一个量就够（② 的 f，或直接压成一维）
需要「前一个位置选没选」         → 必须两个量（③）
答案的「结尾位置」本身不确定     → 需要「必以 i 结尾」这种受约束量，
                                  且答案要遍历取 max（①）

① 和 ② 其实是同一个东西的两种记法：② 的 f 就是把「① 的所有 dp[i] 取 max」这件事提前累积了。

① dp[i] = 必以 i 结尾；答案 = max over all dp[i]    ← 最后遍历一遍
② f[i] = max(f[i-1], g[i])                          ← 边算边累积

所以 ② 省掉了最后那次遍历，答案直接读 f[n-1]，通常更省心。

③ 在一维上常能压缩成 ②，198 就是现成的例子：

skip[i] = max(rob[i-1], skip[i-1]) = dp[i-1]
rob[i]  = skip[i-1] + v            = dp[i-2] + v
→ dp[i] = max(dp[i-1], dp[i-2] + nums[i])      ← 两个量塌成一个

但树上压不了（见 337 的反例：从 f(L) 反推不出 h(L)）。能不能压缩的判据是：「不选前一个」这件事，是否恰好等于「问题缩小一格」。链上成立，树上不成立。

③ 的推广是「状态机 DP」——它本质不是「选/不选」，而是「当前处于哪个阶段」，阶段可以多于两个：

所以「必须选 i / 必须不选 i」只是状态机 DP 最简单的两状态情形。遇到「有额外限制导致不能随便转移」的题（冷冻期、手续费、交易次数上限），先想能不能画成状态机。

• 动态规划编程模板

一种是递归型加hashmap的记忆化搜索；一种是是构造型，构造型的以0为结尾，然后构造以1为结尾，每次x依赖于前面以0到x-1为结尾中的最优解。

• 常见题型以及应对

1. 多个元素相加等于target的组合数

（1）元素是独特(distinct)的，且元素可以重复选，且[1,2]和[2,1]都算答案(本质是考虑排列顺序!)。

解：这种题目的模型就是爬楼梯，爬楼梯的走法就是答案，每次都多少步是有限制的，但是可以重复。先爬两步再爬一步和先爬一步再爬两步是不同走法情况。

解就是看到target的最后一步有几种走法。

（2）元素是独特(distinct)的，且元素可以重复选，但[1,2]和[2,1]算重复情况，只能选一种（本质是只考虑组合！不考虑排序！）。

解：这种题目的模型就是完全背包（物品可以重复选，价值为1）。例如找零钱，在1+2等于2+1的情况下，总的来说都是价值为3，所以算重复情况。

完全背包的解法是新加入一个维度：可选数字的集合（以0开始并以i下标为结束的集合），相当于每次比之前多考虑一个新加入的元素。

这样每一步当前物品的选择都是基于之前的元素的所有选择情况决定的，也就是说，先考虑1，再考虑2，就避免了出现[1,2]和[2,1]这种重复的情况。

物品可以重复选的时候，递推公式里面，target除了依赖上一层集合不选当前i元素直接过来的，而且要依赖同一层之前计算的多个结果（也就是基于该值反复选第i个元素累加得到target)。

（3）元素不一定独特的，但是元素只能选一次，[1,2]和[2,1]算重复。

解：这种题目模型是01背包（价值为1）。由于[1,2]和[2,1]算重复，01背包仍然需要第二维的信息。递推公式里面，target除了依赖上一层集合不选当前i元素直接过来的，或者选择当前的i，也就是减去i的之前计算的结果 ，如何保证是01选择呢？答案是：选i的时候，结果是从上一层没有i的情况过来，也就是dp[i][j] = dp[i - 1][j - nums[i - 1]]，而不是dp[i][j] = dp[i][j - nums[i - 1]]。

总结：如果 [1,2] 和 [2,1] 算重复（即只看组合、不看顺序），才需要二维背包（多出「可选物品集合」这一维）；如果算作不同答案（即看排列），一维的爬楼梯模型就够了。

实操上最关键的一条：降到一维之后，两重循环谁在外层，决定了你算的是组合还是排列。

道理就是：外层是物品时，一个物品被彻底处理完才轮到下一个，天然强制了「先考虑 1 再考虑 2」的固定次序，[2,1] 这种逆序组合根本没机会产生；外层是容量时，每个容量下所有物品都会被试一遍，顺序信息就被保留下来了。

另一条容易记反的：一维滚动时容量循环的方向。

01 背包倒序，是为了让 dp[j - w] 还保持着上一层的值（保证物品只用一次）；完全背包正序，恰恰是为了让 dp[j - w] 已经是本层的新值（这样才允许同一件物品被反复选）。两者方向相反，写反了答案就错。

PS. 要考虑当前加入的元素对之前所有状态的贡献，其中状态甚至可以是子最优解。

• 二维DP

二维DP就是填表游戏：

有两个维度，可以想象是一个二维的表格，行是第一个维度，列是第二个维度。二维DP问题就变成一个如何填这个二维表的问题。

画出这个二维表的时候，不要被维度的具体数值限制住，例如frogJump这一题，第二个维度是frog上一步跳过来的长度k，

这个k是不明确的，每次大小和上限都未知。但是，不重要，知道这个是整数就可以了，可以把列的数量看作是无限的。

实现的时候，再来具体考虑，如果第二个维度不是明确的，而是动态生成的（例如frogJump），那么就采用数组，或者集合，每次往里面加入就行，但本质就是填格子（格子不需要连续）。

如何填表：一般来说，就是一行行的按顺序考虑，例如，对第i行，考虑有所有的列j的情况，这里有意思的是列的考虑不一定需要按顺序，但行一定要按顺序考虑。

第i行的时候，要考虑两种情况：

第一种是当前的第i行的所有的可能性，也就是所有的j，可以完全从第i-1行的所有可能性推导过来；

第二种是当前的第i行的所有的可能性不一定完全从第i-1行所有可能性过来，但可由之前所有的情况推导而来（想象这一行由上面多行推导过来）。

例如frogJump，第i步的坐标是完全从第i-1步的坐标过来吗？显然不是的。但是这里的诀窍是，虽不是，但还是要按顺序来考虑i，

因为，第i步的坐标还是可从之前的所有可能性推导过来。还以frogJump为例，虽然第i步我们不知道怎么从哪一个i过来，但是可以在之前每个i具体单元计算的时候，

就可以把到达第i步的情况算出来。

第一种情况举例：

（1）背包问题。背包里面第i-1行考虑集合{a1, a2,…, ai-1}的所有情况，第i行考虑集合{a1, a2,…, ai}的所有情况。

这样，第i步完全可以由第i-1步推导过来，因为是基于之前的所有1到i-1的情况里面，加上一个新元素ai进行考虑。

对这个新元素ai的考虑就是，选或者不选它，不选的话，问题和i-1就是一样的了；选的话，再考虑对于一个第i行的具体j（也就是具体一个背包大小），选择ai会导致

占ai空间的情况。

（2）房子上色问题。房子不能和上面一个房子有冲突。这种就是当前一步完全可以之前一步推导过来。这里面不太容易看到的点就是，

之前一步的问题就是这个问题的子问题，也就是规模更小的同样问题。

特殊的表格：

有的时候，这个表格里面有些元素明显是不符合要求的，例如最长回文串（5，516）里面，这个二维表格实际上应该是三角形。

而且，很难在整体上考虑每一步的推导，但是这一题直觉上写推导式相对简单些。

具体题目

5. Longest Palindromic Substring

题意：求字符串中最长的回文串。

解：

方法一：动态规划。dp[i][j]表示下标i到下标j的字符串是否回文，最先看i和j是否相等，如果相等，则是回文串（因为是一个字符）。然后看i和j之间的差值是不是1，如果是，说明此时是两个字符的串，也就是看s[i],s[j]是否相等，相等则是回文串。最后看i和j之间的差距是2以上的，要看s[i],s[j]是否相等，以及i+1到j-1之间是否回文，也就是说dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]。 计算顺序是：作图可知，每个格子依赖自己左下方的格子,且一开始初始知道的值是对角线，因此，可以从左到右从上到下一列列的来计算，也可以自下向上，从左到右一行行的计算。扫描时候，顺便记录最长子串且回文的起始下标和长度，最后截取出来作为答案即可。

方法二：每个字符作为中心进行扩展，看能组成的最长回文串，保存一个全局变量最大长度即可。扩展的时候，分为奇数扩展和偶数扩展两种情况。第一种是把当前字母作为中心，第二种，把当前字母和下一个字母作为中心。

PS. 此题动态规划思路的模型就是，把母串拆成n^2个子串，然后从两边扩充这些子串达到较大的子串，最终得出答案。

此题中心扩展的思路就是，子串中以某个元素作为基点扩充，最终答案必然存在于其中一种情况中。

516. Longest Palindromic Subsequence

题意：此题和第5题不同之处在于，subsequence不是substring，而是可以不连续的字符组成的子串。

解：动态规划。一开始想到dp[i]表示0到i的最长回文串，但是发现dp[i + 1]不太好使用dp[i]，那么马上升级维度，即采用二维的思路： dp[i][j]表示下标i到下标j区间内最长的回文串。

思考dp[i][j]怎么缩小成子问题，考虑的关键点是s[i]和s[j]的关系：

两种情况，一种是s[i] == s[j]，有dp[i][j] = dp[i + 1][j - 1] + 2;

另一种是s[i] != s[j]，那么意味着dp[i][j] = max{dp[i + 1][j], dp[i][j - 1]}。

实现细节，仔细分析i，j与i + 1和j - 1的关系，先画出二维数组:

其中：二维数组的有一半不需要考虑，因为i <= j。 基本情况：如果i == j， 那么dp[i][j] == 1。 最终结果：右上角的这个格子。

可知，每个格子依赖的是它的左边格子和它的下边格子。所以，编码时候循环顺序是： 纵坐标定义为i，从下到上，i从n到0；横坐标定义为j，从左到右，由于j >= i，所以是从i到n。

这个流程大概是这样的：每次计算出一些碎片，然后马上扩大区间，根据条件把问题缩小，变成已经计算的碎片。

139. Word Break

题意：能否恰好把串切分成单词，根据单词集合，单词可以重复，也不要求全部使用到。

解：动态规划。定义dp[i]表示0到i的串是不是可以切割，dp[N]是最终结果。首先，从i往前看，如果刚好能组成一个单词（单词集里面任何一个），那问题就变成子问题了， 只要其中的一个子问题能走通，那么当前下标对应的子数组结果就能走通为true。

topdown的方法就是从起点看，能走到那些地方j，然后问题缩减为dp[j]表示j到N的串，这是一种没有记忆的深度搜索，消耗大量时间。

PS. 难的地方在于，要设置一个起点，也就是空串dp[0] = true来保证一个单词是一个子串的时候，也为true。

517. Super Washing Machines

题意：给你一个数组，每个元素表示一台洗衣机洗的衣服数量。然后现在每台机器可以一回合移动一件衣服到相邻的机器（也就选择向左或向右放一件， 衣服数量为0的洗衣机无法移动）。问最少需要几个回合后，可以让所有机器洗衣数量相等，也就是所有数组的值相等。如果做不到，那么返回-1。

解：首先，如果衣服数量总和余洗衣机的数量不为0，那么说明无法平衡，因此返回-1。其次，

把衣服数量当作波峰波谷来看，一个波峰如果从一个方向（例如向右）出发，平均每回合可以把自己的多余的1（比平均值多）传到右边任何一个点。例如[3,0,0,1]。3传给旁边的0，虽然旁边的0一开始是不能传的，但是0变1后就可以继续传给右边了，

所以说，例如3比最终平均值1大2，在向右传递两次的情况下，平均上每次都可以把1个盈余的部分放入任何右侧亏欠1的部分。

使用L来记录某个元素为基准点的左边所有元素（不包括当前元素）所有机器距离平均值缺少的衣服数量，R来记录当前访问元素的右边所有元素（不包括当前元素）所有机器距离平均值缺少的衣服数量。如果L和R都大于0，说明当前元素是波峰，当前元素向两侧输送元素的过程中，由于一次只能向一个方向输送一个，因此如果以当前元素作为起点来进行传输并达到平衡，那么次数将是L+R。

如果L和R一正一负，那么说明自己是波峰或者波谷。例如abs(L) < abs(R)，L < 0,R > 0，那么说明自己是波峰，如果以此起点传输到平衡，那么是左边加上自己的盈余部分移到右边作为结果，其实等于右边abs(R)。

总之，一正一负这种情况，结果是max(abs(L), abs(R))。

如果L和R都小于0，说明当前元素是波谷。那么两边元素可以同时向自己进行运输，所以此时结果取决于慢的那一侧，也就是max(abs(L), abs(R))。

然后，我们对每个元素作为基准点，考虑一遍运输，然后从中选出最少的次数作为结果即可。

使用动态规划中的累加数组来减少左右和重复计算。

53. Maximum Subarray

题意：求包含正负整数的arry最大subarray的大小。

解：

方法一：先计算出前缀和数组，发现其中pair中相减（下标大的减下标小的，或者说右边的减去左边的）最大的那个就是答案。看似需要n^2时间，但是可以使用一个变量记录左侧遇到的最小值，然后把当前扫描的值都和之前的最小值减一下，得出一个答案候选值，这样只需要n时间。

该方法前缀和数组消耗O(n)空间。可以使用滚动数组来减少空间为O（1）。

方法二：动态规划。分治法把问题化简为子问题，然后记录子问题中间值从而减少重复计算来达到优化。问题f(i)分解为两个问题：一个是该最小数组一定包含最后一个数nums[i]，另一个是该最小数组一定不包含最后一个数。 可以知道，问题的解就在于两个问题中。第二个问题中，我们很容易知道f(i) = f(i - 1)；对于第一个问题，我们先将它的解记为g(i)，那么我们有 g(i) = max {g(i - 1) + nums[i], nums[i]}，理解：子数组是要连续且一定包含nums[i]，所以问题分解为：一，不选倒数第二个元素，也就是只选最后一个；二，要么也选倒数第二个，也就是g(i - 1)问题加上最后一个元素nums[i]。

总之，公式是两条：f(i) = max {f(i - 1), g(i)}，其中 g(i) = max {g(i - 1) + nums[i], nums[i]}。合起来就是说，f(i)的解是 f(i - 1)、g(i - 1) + nums[i]、nums[i] 三者中最大的那个。 要求f(i)，那么从计算f(0)开始，计算f(1), f(2), … f(n)，每一步都用到之前计算结果。

上面的公式在编程时候可以空间简化为全局最优和局部最优只需要分别保持一个变量就可以了，由于他们都是只依赖前一个值。

方法三：动态规划。考虑必须以某下标结尾的情况，dp[i]表示元素0-i，且必须包含第i个元素作为最后一个元素的解，那么我们知道，最终答案一定是某个dp[i]。而dp[i]要么和i-1相连，要么就是自己单独作结果（不被之前的元素拖累）。

PS. 使用动态规划方法的缺点是不知道这个最大子数组的起始和结束下标。

91. Decode Ways

题意：A到Z分别使用1到26表示。现在给出一个数字串，求可以所有可能的字母组合数量。

解：此题不需要求解具体的组合，可以使用动态规划可以求解。

dp[n]表示以index n为下标为结尾的串的组合数。该问题拆解为两种问题，一种是最后一个数字作为一个字母的情况，另一种是最后两个数字作为一个字母的情况。

有公式：dp[i] = combination(s[i]) * dp[i - 1] + combination(s[i - 1], s[i]) * dp[i - 2]。

考虑数字串的最后一位的组合。如果最后一位不为0，那么combination(s[i]) == 1，否则combination(s[i]) == 0。再看最后两位（一定要两位一起看！）对应的数字，如果是[10, 26]，那么combination(s[i-1], s[i]) == 1，否则combination(s[i-1], s[i]) == 0。

看基本情况：dp[0]，那么看num[0]是否是1到9，如果是，那么dp[0] = 1，否则dp[0] = 0; 在看dp[1]，如果拆散了来看，其实情况非常复杂，01到09是0，10是1，11到19是2，20是1，21到26是2，26到29是2，30是1，… 但是实际上，需要这么考虑：如果num[1]是1到9，那么说明dp[1]至少和dp[0]一样，在来看num[0]和num[1]一起的组合是不是大于等于10，小于等于26，是的话说明dp[1]多了一个可能。

PS.此题中。“01”的decode方式是不合法的，也就是说不能将01当作1。不能只考虑最后两位的组合，而是要先考虑最后一位的组合，再考虑最后两位的组合。另外，边界条件要注意：看输入字符串是否为空，或者长度小于2。

另外，此题状态只与前两个数有关，可以使用滚动数组将空间复杂度优化到O(1)。

639. Decode Ways II

题意：此题与91不同之处在于，可以使用’*‘表示1到9中任意一个数。

解：dp[i] = combination(s[i]) * dp[i - 1] + combination(s[i-1], s[i])*dp[i - 2]。 解题公式与91完全一样，不同之处在于组合数变得更加多样。可以单独设计一个计算组合数的函数。

现在来分析组合情况，考虑一个数作为一个数字的情况，也就是combination(s[i])的情况：当s[i] == ‘0’，那么combination(s[i])==0；当s[i] == ‘*‘，那么combination(s[i])==9；当s[i] 属于1到9，那么combination(s[i])==1。

考虑两个数作为一个数的情况：如果是’*‘，那么combination(s[i-1], s[i]）==15，因为第一个作为0考虑的时候，其实是非法的，也就是说两位数情况不存在0到9。

如果是’*digit’，那么digit属于0到6的时候，combination(s[i-1], s[i]）== 2，否则，combination(s[i-1], s[i]）== 1。理解就是digit属于0到6的时候，存在1+digit和2+digit两种情况。

如果是’digit*‘，那么digit为‘1’的时候，combination(s[i-1], s[i]）== 9，如果digit为‘2’的时候，combination(s[i-1], s[i]）== 6，否则combination(s[i-1], s[i]）== 0。

其余的情况就是只有数字的情况，与91题一样。

PS.可以使用滚动数组优化空间从O(n)到O(1)。另外，此题结果的数可能很大，因此题目要求返回结果mod 1000000007。

650. 2 Keys Keyboard

题意：一开始只有一个A，只有拷贝粘贴两种操作，求到达n个A所要经过的步数。

解：此题使用动态规划，n可以从之前任意一个数过来。 例如12，那么经过3的拷贝加粘贴3次，也可以是4拷贝1次粘贴2次，也可以是6复制1次粘贴1次，也可以是1通过复制1次粘贴11次达到。其中到达3，4，6需要多少步是一个子问题，之前计算过了，所以要从中间选择最小的。 公式就是dp[i] = min (dp[j] + i/j), 1 <= j <= i / 2 && i % j == 0。 还有优化方法就是：j满足i % j == 0，且越大，一定不小于j比较小的，所以j从大到小遇到第一个i % j == 0的就直接返回。

PS.此题是典型的整数n从之前任意一步较小的过来的动态规划模型。

651. 4 Keys Keyboard

题意：一开始是空，有四种操作：打一个字符A、全选、复制、粘贴。给出操作步数N，求能打出的最多的A数。

解：动态规划。例如N=7，只是把3个A粘贴了两遍。长远来看，操作步数为k时候打印最多的A的模式就是：AA… + 全选、复制、粘贴、粘贴…。这种模式中只可以全选复制一次，因为之前的AA..里面可能包含更多的全选复制，但是我们只考虑最后一步到达的模式，也就是只全选复制一次，粘贴多次的情况。

所以操作步数为k时候的最优解取决于前面i步生成的A，加上最后面k-2-i步粘贴次数的选择。理解：前面的A由操作步数为i来最大化生成。结果就是第i步的结果增大了(k - 2 - i) 倍，i的选择范围是[1，k-3]。另外就是：dp[k]至少是k，因为可以通过全进行输入A操作得到。

建立动态规划数组dp，dp[i]表示只有i步的最大结果，那么方程可以列为：

dp[k] = max {k, max { dp[i]*(k - i - 1)} }, 1 <= i <= k-3。其中也可能出现没有全选、复制、粘贴，而全部是直接打印A得出最大结果的情况。

198. House Robber

题意：数组里面下标代表房子index，值大小代表能偷的价值（大于等于0），相邻房子不能偷，求最大能偷多少。

先排除一个错误直觉：不能只比较奇数位总和和偶数位总和。反例 [2,1,1,2]——选开头和结尾的两个 2，总和 4 才是最优解，而它既不是全奇数位也不是全偶数位。

统一骨架：两状态 DP（本系列 198／213／337 共用）

这个骨架是 198、213、337 三题共同的形式，先建立它，后面两题就只是换个「邻居」。

每个位置只有两种状态，而约束只有一条——「选我」要求「邻居不选」：

rob  = 选当前这个的最优解
skip = 不选当前这个的最优解

rob  = (邻居的 skip) + 当前值           选了我 → 邻居必须不选
skip = max(邻居的 rob, 邻居的 skip)      不选我 → 邻居随意
答案 = max(rob, skip)

对一维数组来说，「邻居」就是前一个位置，滚动两个变量即可，空间 O(1)：

int rob = 0, skip = 0;
for (int v : nums) {
    int nRob  = skip + v;
    int nSkip = Math.max(rob, skip);
    rob = nRob; skip = nSkip;
}
return Math.max(rob, skip);

方法一（推荐）：dp[i] 表示前 i 个房子的最优解

dp[i]表示0到i这些房子的子问题的解（偷或不偷第i个房子都考虑在内），分两种情况：

• 偷第i个房子：dp[i] = dp[i - 2] + nums[i]
• 不偷第i个房子：dp[i] = dp[i - 1]

所以公式是 dp[i] = max { dp[i - 1], dp[i - 2] + nums[i] }，答案直接就是 dp[n-1]，不需要再对所有 dp[i] 取 max。

这其实就是上面两状态骨架的压缩形式，推一下就知道：

令 dp[i] = max(rob[i], skip[i])
则 skip[i] = max(rob[i-1], skip[i-1]) = dp[i-1]
   rob[i]  = skip[i-1] + nums[i] = dp[i-2] + nums[i]
代入 → dp[i] = max(dp[i-1], dp[i-2] + nums[i])   ✓

也就是说，一维公式是把 skip 消掉之后的结果。这个代换在一维上成立，但到了 337（树上）就不成立了——那里必须把两个状态都往上传，原因见 337。

时间 O(n)，用滚动数组空间 O(1)。

方法二：dp[i] 表示「必须偷第 i 个」——不推荐

也可以定义 dp[i] 为必须偷第i个房子时的解，这相当于只保留骨架里的 rob、丢掉 skip。

此时 i-1 不能选，而 i-2 不一定选（例如 {2,1,1,2}，最后一个 2 如果搭第一个 1 就得不到最优），所以要在 dp[i-2] 和 dp[i-3] 中取较大者：

dp[i] = max { dp[i-2], dp[i-3] } + nums[i]

（为什么不用考虑 dp[i-4]？因为房子价值非负，若选 dp[i-4]，那么 i-4 还能再搭上 nums[i-2]，也就是 dp[i-4] <= dp[i-2]。）

这个定义的三个代价，解释了为什么推荐方法一：

1. 转移变成三项，还要额外论证「为什么不考虑 dp[i-4]」
2. 答案必须对所有 dp[i] 取 max，不能直接读 dp[n-1]
3. 依赖「房子价值非负」这个前提，有负数就不成立

方法一／两状态骨架一条都不占。

PS. 两状态这种形式之所以自然，是因为本题每个元素只存在「选和不选」两种情况；而最大子数组和那类题是连续型的，选了之后还要看和前面连不连，属于另一种模型。

followup：如果数组里有负数怎么办？负数一定不会选——选了它不但没收益，还让旁边两个不能选，一定是亏。公式形式不变，只要在值为负时不走「偷第i个」这一支即可（等价于把负数当 0）。

213. House Robber II

题意：在198题的基础上，房子现在围成一圈。

解：成环之后，多出来的唯一约束是：第一间和最后一间相邻，不能同时选。除此之外和 198 完全一样。

于是关键一步是这个推理：

第一间和最后一间不能同时选 ⟹ 任何合法方案必然「不选第一间」或者「不选最后一间」（至少一条成立）。

因为”两间都选”被禁掉了，剩下的可能只有三种：只选第一间、只选最后一间、两间都不选。这三种情况都满足「至少有一间没被选」。

所以只需要跑两次 198：

情况 A：不选第一间 → 在 nums[1 .. n-1] 上跑 198
情况 B：不选最后一间 → 在 nums[0 .. n-2] 上跑 198
答案 = max(A, B)

严格说，正确性要证两个方向：

方向一（不漏）：任何最优解都会被某一支算到。

设 S 是环形问题的任意合法方案。因为 0 和 n-1 不能同时属于 S，所以至少有一个不在：

• 若 0 ∉ S：则 S ⊆ {1..n-1}，且 S 内部没有线性相邻的两个，这正好是 nums[1..n-1] 上的一个合法线性方案 → robLinear(1, n-1) >= value(S)
• 若 n-1 ∉ S：对称 → robLinear(0, n-2) >= value(S)

所以两者的 max >= 最优值。

方向二（不多）：两支算出的每个方案都真的合法。

设 T 是 robLinear(1, n-1) 统计到的任意方案。T 的线性相邻约束由线性 DP 本身保证；而环形多出来的那条约束是「0 和 n-1 不能都选」——由于 0 ∉ T，这条自动满足。所以 T 是环形合法方案 → robLinear(1, n-1) <= 最优值。另一支对称。

所以两者的 max <= 最优值。

两个方向合起来，等号成立，证毕。

顺便回答一个常见疑问：如果最优解既不选第一间、也不选最后一间呢？那它会被两支同时算到。这个重叠无害，理由正是上面两个不等式夹出来的：

两支各自都 <= 最优值（方向二）
两支的 max >= 最优值（方向一）
→ 重复计算不可能把结果推到最优值之上

这就是「覆盖足够、不必划分」的全部含义——重叠只会让某个合法值被重复报出，而 max 对重复免疫。

注意 A 和 B 是有重叠的（例如 {1,2,3,4,5} 拆成 {2,3,4,5} 和 {1,2,3,4}，两者都包含 {2,3,4}），但重叠不影响正确性——我们取的是 max，同一个方案被算两遍没有副作用。这里要的是「覆盖」，不是「划分」。

这一点值得单独记住，因为它是一条通法：求最优值的问题，拆解情况时只要求并集覆盖全部合法方案，不要求不重不漏。很多人卡在本题，就是下意识想做”不重不漏的划分”，然后发现怎么分都分不干净。

但要注意这条只对”求最优值”成立。按”要什么”分三档：

所以”15 要去重、923 要数清楚、213 可以重叠”不是三种要背的规矩，而是同一条判据的三个分支：先问「我要的是极值、数量、还是内容」。

另外要理解清楚：「不选第一间」并不意味着「一定要选最后一间」。情况 A 跑的是 198，它在 nums[1..n-1] 上自由决定选谁，完全允许最后一间也不选。所以”两间都不选”这种方案，在 A 和 B 里都会被考虑到，不需要单独列一种情况。

边界：n == 1 必须特判

n == 1 时，两个子区间 nums[1..0] 和 nums[0..-1] 都是空的，各返回 0，答案就成了 0，而正确答案是 nums[0]。

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];                  // 必须特判
    return Math.max(robLinear(nums, 0, n - 2),   // 不选最后一间
                    robLinear(nums, 1, n - 1));  // 不选第一间
}

小 n 逐个验一遍（怀疑通常出在这里）：

所以只有 n == 1 需要特判，n >= 2 公式本身就是对的。

337. House Robber III

题意：输入是二叉树，值都大于等于0，相邻结点不能都选，最终能偷最大为多少。

解：本题就是 198 那个两状态骨架搬到树上，「邻居」从「前一个位置」变成「左右孩子」。

推荐解法：每个节点往上传两个值

沿用 198 的两个状态，只是记号换成 g／h：

• g(root)：一定选 root 时，以 root 为根的子树的最优解（对应 198 的 rob）
• h(root)：一定不选 root 时的最优解（对应 198 的 skip）
• f(root) = max { g(root), h(root) }，答案就是 f(整棵树的根)

转移：

g(root) = root.val + h(root.left) + h(root.right)
h(root) = max{ g(root.left), h(root.left) } + max{ g(root.right), h(root.right) }

• g：选了自己，两个孩子都必须不选，所以加的是孩子的 h。
• h：不选自己，不代表孩子必须选——孩子选或不选都自由，所以要在每个孩子内部各自取 max 再相加。这一点最容易想漏。

基本情况：叶子 g(leaf) = leaf.val、h(leaf) = 0；空节点 g(null) = h(null) = 0。

编码时一次后序 DFS，每个节点返回一对值（选 / 不选），父节点拿到两个孩子的两对值就能直接算出自己的两个值。一遍搞定，不需要任何记忆化。

和 198 并排看，完全同构：

差别只是「邻居」从一个变成两个，每项加法从一项变成两项。

为什么树上不能像 198 那样压缩成一个值

198 里可以只维护一个序列 dp[]，因为有这个等号：

skip[i] = max(rob[i-1], skip[i-1]) = dp[i-1]

也就是说，「不选第 i-1 个」恰好等于「问题缩短成前 i-2 个」——链的结构让「跳过最后一个」和「边界回退一格」是同一回事，所以 skip 不必单独记，它藏在同一序列更早一项里。

树上这个等号不成立：「不选节点 L」不等于任何一棵子树的解，因为 L 的孩子还在，只是 L 自己不选，这不对应任何「更小的子树」。

反例：

        root = 1
          |
        L = 100
        /           3        4

g(L) = 100 + h(3) + h(4) = 100
h(L) = max(g3,h3) + max(g4,h4) = 3 + 4 = 7
f(L) = max(100, 7) = 100

算 g(root)（选 root，故 L 必须不选）：

正确：g(root) = 1 + h(L) + ... = 1 + 7 = 8
若手上只有 f(L)： = 1 + 100 = 101   ← 非法，root 和 L 同时被选了

f(L) 里「含着 L 自己」，而我们要的恰恰是「不含 L」的那个值，从 f(L) 反推不出 h(L)。反过来只传 h 也不行——算 h(parent) 时需要 max(g(L), h(L))，又缺 g。所以两个值缺一不可。

另一种写法：只用 f，但要配记忆化（不建议）

如果坚持每个节点只维护一个 f，那么拿不到 h(L)，只能把它展开成孙子层：

f(root) = max { f(root.left) + f(root.right),                            // 不选 root
                root.val + f(L.left) + f(L.right) + f(R.left) + f(R.right) }  // 选 root

这么写是对的，但必然产生大量重复子问题——f(L.left) 在算 f(L) 时也会被算一遍，所以必须配 hashmap 做记忆化，否则指数级爆炸。

它需要记忆化的根源就是「只传一个值」：拿不到 h，就只能把 h 展开成孙子的 f，于是同一子问题被反复求解。推荐解法把 h 直接传上去，从根上避免了这件事。

所以这种写法只作为理解的参照，实际不建议使用：既要多写一个 memo，又比推荐解法慢，还得多算一层孙子。

PS. dp题目自下而上的编码，对于一维数组来说，就是从下标0开始计算，而对于二叉树来说，也就是从叶子节点开始往root计算。

174. Dungeon Game

题意：MxN矩阵要从左上角的格子走到右下角的格子（只能向右走或向下走），遇到正数加血，否则减血，血量不能小于等于0。现在求英雄最少初始血数就可以到的右下角格子救公主。 英雄在第一个格子和最后一个格子也会掉血或者加血。

骨架（先记这六行）

① 约束「血量至少 1」是未来的：能不能活取决于后面还要掉多少血
   → 正向（从起点往终点）推不出来 → 状态必须定义成「从这里出发」
② dp[i][j] = 从 (i,j) 出发、走到终点所需的最少初始血量
③ need     = min(dp[i+1][j], dp[i][j+1])     两条路取「需求小」的那条
   dp[i][j] = max(1, need - nums[i][j])       max(..., 1) 就是那条约束的全部体现
④ 扫描方向：自下而上、从右至左
⑤ 答案 = dp[0][0]
⑥ 边界：加一行一列 dummy，全填 INT_MAX，只把 dp[M][N-1] = dp[M-1][N] = 1
   INT_MAX = 「此路不通」，1 = 「这里是出口」；出口只有一个，所以只有终点的邻居能填 1

解：为什么必须倒着推——「血量不能低于 1」这个约束是未来的：英雄此刻能不能活，取决于后面还要掉多少血。如果按「从起点走到 (i,j)」来定义状态（也就是依赖 dp[i-1][j] 和 dp[i][j-1]），这个信息根本还不存在，推不下去。所以状态必须反过来定义成「从 (i,j) 出发到终点所需的最少初始血量」，依赖的是下方和右方（dp[i+1][j] 和 dp[i][j+1]）。这正是本篇总体思路里「状态定义的方向」那一节说的情形，而且是最纯粹的一个例证。

规定dp[i][j]表示从i，j处出发到达终点dp[M - 1][N - 1]的最少初始血量。关键难考虑的点在于英雄血量低于1就直接gameover，公式不好一眼写出来，那就从基本情况开始推， 显然，如果英雄已经在[M - 1][N - 1]位置上，那么假设最后一个格子值是-5，那么dp[M - 1][N - 1] = 6，因为6 - 5 = 1 > 0才可以生存（0不可以！） 假设最后一个格子的值是5，那么英雄只要在来的时候活着就行，就是1； 总结：如果nums[M - 1][N - 1] >= 0，那么dp[M - 1][N - 1] = 1；如果nums[M - 1][N - 1] < 0，那么dp[M - 1][N - 1] = 1 - nums[M - 1][N - 1]。

在看[M - 1]这一行，每个值都是依赖右侧的值，例如看dp[M - 1][N - 2]，假设nums[M - 1][N - 2] = -1，那么首先在这个位置上就要掉血，如果掉完血还要活到最后一个格子， dp[M - 1][N - 2] = 6 + 1 = 7才行，总体来说，如果nums[M - 1][N - 2] < 0，那么必然有dp[M - 1][N - 2] = dp[M - 1][N - 1] - nums[M - 1][N - 2]； 再来看，如果nums[M - 1][N - 2] = 1，那么英雄在这个位置上可以加血，也就是说，dp[M - 1][N - 2] = dp[M - 1][N - 1] - nums[M - 1][N - 2] = 5； 注意，难考虑的盲点来了：在nums[M - 1][N - 2] > 0的情况下，dp[M - 1][N - 1] - nums[M - 1][N - 2]是存在小于0的可能性的，而这个不能成立（game over！）

所以，nums[M - 1][N - 2] > 0的时候，分两种情况考虑，一是dp[M - 1][N - 1] > nums[M - 1][N - 2]，此时dp[M - 1][N - 2] = dp[M - 1][N - 1] - nums[M - 1][N - 2]； 二是dp[M - 1][N - 1] <= nums[M - 1][N - 2]，这种情况是什么意思呢？这种意思是英雄在这个位置上得了大量的血，因此，一开始英雄只要是活着就可以了，也就是说，这种情况下， dp[M - 1][N - 2] = 1（注意这里算的是 N - 2 这一格，不是 N - 1）。

把两种情况合起来就是一条式子：dp[i][j] = max(1, dp[下一格] - nums[i][j])，那个 max(…, 1) 就是「血量不能低于 1」这条约束的全部体现。

同理，考虑[N - 1]这一列。

然后，就是考虑中间的dp[i][j]，区别就是它有从下边走和从右边走两种选择。两条路里取需求小的那条（因为我们要的是最少初始血量），然后套上面那条统一式子：

need     = min(dp[i + 1][j], dp[i][j + 1])
dp[i][j] = max(1, need - nums[i][j])

自下而上、从右至左进行扫描，答案是dp[0][0]。

dummy 行列的初始值：两个值各代表什么

编码时可以在矩阵下方和右边各加一行（列）dummy，把「基本情况」和「边界」全部编码进数据，省掉单独的初始化代码。填法是：

dp 开成 (M+1) x (N+1)，全部填 INT_MAX，然后只把 dp[M][N-1] 和 dp[M-1][N] 填 1。

为什么是这两个值——dummy 不是占位符，它们各有明确含义：

有了这两个含义，终点那一格就会被统一公式自己算出来：

dp[M-1][N-1] = max(1, min(下方, 右方) - nums[M-1][N-1])
             = max(1,   min(1, 1)    - nums[M-1][N-1])
             = max(1,        1       - nums[M-1][N-1])

这正是上面手推出的基本情况。所以不需要单独写一行特殊处理终点。

为什么只有终点旁边那两个能填 1——因为出口只有一个：英雄只能从右下角走出地牢，不能从中途向下或向右”跳出去”。

如果把整行 dummy 都填 1，就等于允许他提前离场。反例 dungeon = [[-100, -100]]：正确答案是 201（先掉 100 需 h>=101，再掉 100 需 h>=201）。

• 正确填法（dp[1][0] 保持 INT_MAX）：dp[0][1] = max(1, min(1,1)+100) = 101；dp[0][0] = max(1, min(MAX,101)+100) = 201 ✓
• 错误填法（dp[1][0] 也填 1）：dp[0][0] = max(1, min(1,101)+100) = 101 ✗

min(1, 101) 选中了那个假出口——相当于英雄在第一格就从底下溜走了，后面 100 点伤害被整段跳过。

补一点：其实只填一个就够（min(1, MAX) = 1），只设 dp[M][N-1] = 1、让 dp[M-1][N] 保持 INT_MAX，结果完全一样。两个都填是为了对称好读，也免得纠结该填哪一个。

不用 dummy 也行，那就得手算终点，再分三段循环：最后一行（只能往右）、最后一列（只能往下）、中间（两个方向取 min）。四段代码都对，但每段边界都要小心。dummy 版把这四段压成一个双重循环，代价是必须想明白那两个 1 的含义。

注意不会溢出：任何真实格子都至少有一个邻居是已算出的真实值（终点的两个邻居都是 1），所以 need 永远不会等于 INT_MAX，need - nums 不会溢出。

dummy 的本质是：把「基本情况」和「边界」编码成数据，而不是编码成代码分支。 INT_MAX 表示「不存在的路」，1 表示「唯一的出口」。

这个手法在 dp 里很通用——前缀和补一个 sum[0] = 0、链表加 dummy head、区间题两端加哨兵、84 题末尾加高度 0 的哨兵，都是同一件事。

152. Maximum Product Subarray

题意：此题求连续子数组中乘积最大的。

解：动态规划，此题不同之处在于，负数乘以负数得出正数，也就是说，一个最小的负数可能逆袭成最大的数。因此，在子问题中，我们记录以下标i为结束的当前最大数和最小数（可能是负数）。

那么下一个i+1下标的最大数是，前一个最大数MAX[i]乘以自己nums[i + 1]、前一个最小数MIN[i]乘以自己nums[i + 1]、以及自己nums[i + 1]三者之间最大的那个。 同理，最小数是三者中最小的那个(这个容易错！！)。一遍扫描完之后，记录下当前最大的乘积作为结果返回。

如果使用滚动数组的话，记得要把最大数和最小数每次都合适的更新掉。

674. Longest Continuous Increasing Subsequence

题意：寻找最长递增的的substring。

解：此题使用动态规划。dp[i]表示必以下标i为结束的最长递增序列，如果nums[i] > nums[i - 1]，那么dp[i] = dp[i - 1] + 1; 如果nums[i] <= nums[i - 1]，那么说明带上自己连不起来，那就是dp[i] = 1。 答案是其中最大的dp[i]。

可以优化空间O(N)到 O(1)。

377. Combination Sum IV

题意：此题相比于39题，更加多的限制，也就是全是正数，且不含重复元素，元素可以多次使用，求等于正数target的组合。序列不同，例如[1,1,2]和[2,1,1]不算重复的。另外，结果只需要组合的数量，而不需要具体列出组合。

解：此题如果使用常规的dfs，但是此题由于可以选自己，所以必须要排序。但是dfs方法会超时，试想一个[1,2,3]，能组成100的组合实在是太多了，递归必然造成大量重复计算。所以使用动态规划。

由于[1,1,2]和[2,1,1]不一样，那么此题和爬梯子题一样（就是每一步可以走1，2或者3步，然后问爬完梯子有多少种方法），究其本质， 就是朝三暮四不等于朝四暮三，也就是说要考虑时间的维度，先爬一步梯子，在爬两步，和先爬两步，在爬一步在这里认为是不同的，也就是说，考虑的是排列。

这种问题这么考虑：到达target最后一步是通过几种元素，也就是问题递归为target减去最后一个元素的子问题，且是这些子问题答案的总和。

使用bottom up，从1计算到target，只要期间一个数大于任何一个元素，那么就加上，即dp[i] += dp[i - num] if i >= num。

初始条件：dp[0] = 1。

理解：爬梯子里面是从前一步过来或者从前前一步过来，对应此题就是，for循环nums数组，能从一个num过来就过来，不然就拉倒。

PS.(1) target为0的组合数是1，而不是0。意思是全不选的情况。

(2) 自上而下可以先排序，然后在num比i小的时候，后面的num全部不用考虑，直接break。

（3）如果[1,1,2]和[2,1,1]算重复，那么就是二维背包问题。

由于是一个数可选多次，像是一维背包。

322. Coin Change

题意：找零钱，求最少组合硬币数，也就是问最少找多少枚硬币。

解：解决target大小的问题，那么可以先解决所有target - nums[i]的子问题，然后选择其中最小的子问题加1来作为自己的答案。

要注意此题可能会无解，如果是面额不合适，是会出现的，此时应该返回-1。

518. Coin Change 2

题意：此题是求找零钱硬币组合数，与322的关系，322是求组合里大小最小的那个。

和377题(组合四)唯一区别是：[1,1,2]和[2,1,1]算重复。

解：本质是完全背包。完全背包就是物品选择方式次数不受限制。他与只能选一次(01背包)的计算时候区别在于，对于一个物品i，考虑不是选或不选，而是不选或者选1次，选2次…

完全背包中，除了求解的target的维度以外，在加入新的维度：可选元素分别是以0开始并以i下标为结束的集合，相当于每次比之前多考虑一个新加入的元素。

这样每一步当前物品的选择都是基于之前的元素的所有选择情况决定的，也就是说，先考虑1，再考虑2，就避免了出现[1,2]和[2,1]这种重复的情况。

二维背包的第二维度按集合从小到大考虑，本质就是告诉物品之间的选择先的后顺序是需要考虑的。

编码的时候，由于可选的物品数量没有target大，所以习惯性的把物品集合作第一个维度，把target作第二个维度。dp[i][j]表示只用前i种硬币凑出金额j的组合数（注意本题求的是组合数量，求「最少硬币数」的是322，别搞混）。

dp[i][j] = dp[i - 1][j] + all { dp[i - 1][j - k*coins[i]] }。理解：每次新加入一个coin[i]的时候，都有选和不选两种情况：

要么是不选第i个物品，直接继承之前的结果（正上边的一个格子）；

要么选第i个物品，由于可以重复选，其实有k种选择，只要满足j - k * coins[i] >= 0且k > 0（如果等于0，那就是不选）。(完全背包依赖左上方若干格子，01背包是只依赖一个左上方格子)

初始条件: dp[0][0] = 1，理解：在集合为空的且target = 0的时候，默认为找到了一种组合数。同理，dp[i][0] = 1。

递推公式可以优化，考虑其中的all { dp[i - 1][j - k * coins[i]] }，实际上dp[i][j - coins[i]]和all { dp[i - 1][j - k * coins[i]] }是相等的,理解： dp[i][j - coins[i]] = dp[i - 1][j - coins[i]] + all { dp[i - 1][j - m * coins[i]] }，m就比k小1。

这样优化之后，它就只依赖正上方的一个格子和正左侧的一个格子。

PS.

1. 解和377几乎一样，但是看起来两个循环嵌套是反过来的。 也就是说，不是考虑倒数第二步是怎么过来的，而是对每一个硬币，考虑大于等于该硬币的amount的贡献，也就是说一个硬币只会被考虑一次。也就是说对于硬币2，我们考虑他对2到amount的贡献，对于3考虑他对3到amount的贡献，而之前的题目解法是反的，也就是amount == 3的时候，又会把硬币2重复考虑一遍。 对于amount=4，考虑过1对4的贡献了，就是[1,1,1,1],[1,1,2]。后面从2开始考虑的时候，不能用1这个硬币了，如果用了就会产生[2,1,1]这种重复元素。 先使用coins做外重循环，表示一次只考虑一种硬币。

2.背包完全与01背包比较：01背包不可重复选的时候，依赖的是不选和之前一层只选一次过来的，也就是依赖正上方一个格子和左上方一个格子。

1. 硬币的面值需要是独特的，不能重复，否则计算的结果是不对的。

2. 如果优化二维空间到一维，本题（完全背包）容量循环必须是从小到大（正序）。理由见上面的优化推导：优化后的递推依赖「正上方 + 正左侧」，而正左侧是本层的格子，正序才能让它已经更新成本层的新值，从而允许同一枚硬币被反复选。

注意不要和 01 背包记反了：01 背包依赖的是上一层的左上方格子，所以降维后必须从大到小（倒序），才能保证 dp[j - coins[i]] 还停留在上一层、物品只被选一次。参见 416 题的说明。

221. Maximal Square

题意：给出只包含0和1的二维矩阵，求实心1的正方形中最大的面积。

解：这种二维矩阵面积类型的问题，首先就要想到二维累加和的两个技巧： （0，0）（0，1）（0，2）… （1，0）（1，1）（1，2）… （2，0）（2，1）（2，2）… （3，1）（i, j）（i，y）… … … (x, j) (x,y) …

技巧一：求出（0，0）到（i，j）的面积（或者累加和）

使用动态规划，对于dp(i, j)，我们先计算dp(i - 1, j - 1), dp(i - 1, j)和dp(i, j - 1)。 考虑dp(i - 1, j) + dp(i, j - 1)，从面积上看，他们在减去其中的重叠部分，然后再加上(i - 1, j - 1)到(i, j)的部分就等于dp(i, j)。其中(i - 1, j - 1)到(i, j)的部分其实也就是 matrix[i][j]。总结得出公式: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i][j]; 基本情况是：dp[0][0] = matrix[0][0]。

技巧二：求出(i, j)到 (x, y)的面积

公式就是：f[i ~ x][j ~ y] = dp[x][y] - dp[x][j] - dp[i][y] + dp[i][j]。理解：减去两部分，然后把多减去的重叠部分加进来。

结合这两种方法，可以暴力求解每个（i,j）开头的所有可能正方形，看面积是否等于累加和，如果等于，那么就找到一个实心1正方形，时间复杂度O(N^3)。

而此题使用特殊技巧。 思路是：dp[i][j]代表以坐标(i,j)必以右下角结尾的最大实心1正方形的边长大小：

dp[i][j] = 0， 如果matrix[i][j]==0，

如果matrix[i][j]==1，那么看dp[i-1][j-1], dp[i-1][j]和dp[i][j-1]三个中最小的+1。这点几乎很难想到。理解：这一步只是尝试在上一步的基础上加1， 重点参考dp[i - 1][j - 1]，如果它比dp[i-1][j]或dp[i][j-1]大，那么说明要在dp[i - 1][j - 1]基础上加1是不行了，但是可以在最短板处补上1，因为最短处往i，j处必然是全1。 如果dp[i - 1][j - 1]比两者都小，那它就是短板，因为它的外侧必然覆盖满了1。

二维矩阵动态规划题的一个通用思路，那就是考虑临近结点（不止一个，多数情况下是三个）作为子问题被解决后对当前格子的贡献。

编码：基本情况是第一行，第一列先计算出来。

PS.初始化时候，需要初始化第一行和第一列，因为他们能仅凭自己本身元素断定是0还是1。之后沿着从左到右，从上到下的扫描顺序就可以自然的求解出所有dp[i][j]。 可以使用滚动数组优化空间，此题依赖左边、左上、上边三个格子，不能使用之前的滚动数组（之前滚动数组使用一个一维空间就可以）解决法，应该使用两个一维空间，交替使用一维空间就可以了。

673. Number of Longest Increasing Subsequence

题意：求最长递增子序列（LIS）的条数。注意求的是条数不是长度（长度是 300 题），而且子序列不要求连续。

例：[1,3,5,4,7] 答案是 2（LIS 长度为 4，有 [1,3,5,7] 和 [1,3,4,7] 两条）；[2,2,2,2,2] 答案是 5（没有严格递增的对，LIS 长度只有 1，每个元素各算一条）。

解：此题是经典 LIS（300 题）的 follow up。关键是同时维护两个数组：

len[i] = 以 nums[i] 结尾的 LIS 的【长度】
cnt[i] = 以 nums[i] 结尾、长度恰好为 len[i] 的 LIS 的【条数】

初始化：len[i] = 1，cnt[i] = 1（每个元素自己就是一条长度 1 的 LIS）。

转移：对每个 i，遍历所有 j < i 且 nums[j] < nums[i]：

if (len[j] + 1 > len[i]) {          // 发现更长的 → 覆盖
    len[i] = len[j] + 1;
    cnt[i] = cnt[j];                // ★ 是 cnt[j]，不是 1
} else if (len[j] + 1 == len[i]) {  // 长度并列 → 累加
    cnt[i] += cnt[j];
}
// len[j] + 1 < len[i] → 没贡献，跳过

答案：先求 maxLen = max(len[i])，再把所有 len[i] == maxLen 的 cnt[i] 加起来。

时间 O(n^2)，空间 O(n)。

三个要点

（1）覆盖时是 cnt[i] = cnt[j]，不是 cnt[i] = 1。这是本题最容易写错的一处。

理解：「以 i 结尾、长度为 len[j]+1 的 LIS」有多少条？等于「以 j 结尾、长度为 len[j] 的 LIS 有多少条」——因为那每一条后面都能接上 nums[i]，各自变成一条新的。所以是 cnt[j] 条。

反例 nums = [1, 3, 2, 4, 5]：

正确答案 2（[1,3,4,5] 与 [1,2,4,5]）。若写成 cnt[i] = 1，答案会变成 1。

（2）「更长」和「并列」两个分支必须分开。一个负责覆盖、一个负责累加，合成一个 if 必错。

（3）答案要把多个结尾的 cnt 加起来。最长 LIS 可能以不同位置结尾。例如序列 1，2，3，9，8，7 中，最长长度是 4，而 9、8、7 三处都是长度为 4 的 LIS 的结尾，是三条不同的序列，必须累加。

（4）[2,2,2,2] 这种特例：因为要求严格递增，相等的元素之间接不上，所以每个位置都找不到可接的 j，len 和 cnt 全部保持初始值 1，答案就是元素个数。这正是把两者都初始化为 1 的意义。

PS. 本题还有 O(nlogn) 的做法（线段树／树状数组同时维护长度与条数），面试中一般不要求，O(n^2) 足够。

764. Largest Plus Sign

题意：给出二维全1的01矩阵，然后又给出其中坐标为0的数组，问其中最大的十字半径是多大。

解：此题解法是对于每个位置，如果是1，那么查看以该位置为十字中心能够延展到多大的十字，一开始比较迷茫，应该它打破了二维数据dp的常用技巧：以某某坐标为结束的子问题。

因此需要打破常规，让求解的问题变形，回到熟悉的模式，也就是把复杂问题分解为若干简单的问题。

具体来说，此题既然十字形不好处理，那么干脆把十字形看作是四个线段的拼接，这样发现问题居然转化为以某节点为中心向左、向右、向上、向下延展的连续1中最短的那个。

接下来，就考虑如何求解向一个方向上的连续1？如果一个位置，它是0，那么结果也就是0；否则，虽然难考虑，但是我们仍然使用常见技巧，就是依赖它前一个位置的结果，也就是前一个位置结果+1。

所以可以使用动态规划求解。

编码：在自左向右，自上而下的方向的一遍扫描过程种，其实可以同时把向右和向下的结果求出来；同理，反向扫描得出向左和向上的结果。

最后，在进行一次扫描，这次考虑以元素为中心，四个方向哪个最小，那就是多大的十字形。 时间复杂度降为O(n^2)。

PS. 建立四个二维数组保存连续1的信息(4 * n^2)的空间复杂度。空间复杂度可以减少到1个n^2。 关心四个方向中最小的那个，也就是说，使用一个n^2的空间保留最终的结果，四个方向扫描过程中，只需要使用4个临时变量，然后如果该变量比最终结果小就更新（结果数组初始化为n）。扫描过程需要分开计算，不能两个双重循环得出答案，而是需要4个双重循环计算出四个方向的答案。

416. Partition Equal Subset Sum

题意：求正整数数组是否能分成两个相等的部分。

解：此题是01背包问题，因为原问题可以转化为能否挑选出元素，和等于数组总和的一半。

01背包问题的解法套路就是:对于dp[i][j]表示集合{0,1,2,…,i}和target为j的子问题，且最后一件物品考虑i，所以只要考虑dp[i-1][j]以及dp[i-1][j - nums[i]]。最终结果就是dp[nums.size()][target]，表示从集合{0,1,2,…,n}中选，选出target的问题。

此题来说dp数组是bool型，表示能否找到和等于target。

初始条件：target = 0的时候，不管数组是什么，全是true；数组为空的时候，除了target = 0的以外，全是false。

还可以使用滚动数组来减少空间使用，因为dp[i][j]依赖于dp[i-1][j]以及dp[i-1][j - nums[i]]，也就是说，完全依赖于上一层的两个元素，

所以我们不能正的（0到size）滚动计算：如果正序计算后，依赖的两个元素中的前一个已经不在是上一层的结果了，而是最新一层的结果，而倒着计算（size到0）不会覆盖上一层结果。

494. Target Sum

题意：给一个正整数数组，每个数字之前加上正负号，结果等于target，求方案个数。

解：方法一：暴力求解：使用dfs，每次进入一层，无需记录path，只需要把当前层的两个结果转换为下一层，在看最后一层时候，看得出的结果是不是target来判断该路径是否走的通，走的通就加1。

方法二：使用动态规划。 dp[target][i]表示现在题目问题规模是可以变化的，也就是说，target是可变的，i表示i个整数元素的片段，也就是只能使用前i个元素，也就是说，任何一个dp[target][i]都是一个类似的问题，不过规模更小，他不是大问题的一个步骤，而是一个类似的问题，只不过规模更小。 、优化： sum(P) - sum(N) = target sum(P) + sum(N) = sum(nums) => 2 * sum(P) = target + sum(nums) 其中sum(P)表示加正号数集合的和，sum(N)表示加负号的集合的和（取正）。所以存在上面两步的转化。结果就是将原来的问题转化为416类似问题。本质就是01背包。 解法参考416。

注意边界条件： target + sum(nums)为奇数或负数的话结果直接返回0，sum < target时候也返回0。

309. Best Time to Buy and Sell Stock with Cooldown

题意：对一个数组，数组元素表示当天股票价值，现在求最大利润，只不过：

（1）当天只能买或卖,而且只能先买入后卖出，不能一直卖。

（2）卖股票之后，至少要等一天才能买

注意：再次买前必须卖，意思就是买卖是交替的，不能连买两次。

解：一开始以为此题意思是有本金M，每次买卖必是全买全卖，（最后一次卖掉获得的钱 - 本金）除以本金的百分比，也就是利润。

但是通过例子: prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell] 我们知道：如果初始本金100，在第一天买了100股，第二天卖掉，得到本金200，在第四天（价格0？？）买入，第五天卖，那不知道翻了多少倍了。。 所以此题其实要求的是在每天只买入一股或卖出一股的最大收益。

仍采用动态规划，本题是股票系列状态机的一个变形（总纲见《总结（一）》121 题），属于「加状态」那一类。

为什么两个状态不够：基础形式里 hold = max(hold, cash - price)，但 cash 里混着两种情况——「今天刚卖出的」（不能马上买）和「更早就空仓的」（可以买）。max 一取就分不清了。而「能不能买」恰恰取决于「昨天是不是刚卖」这段历史，所以必须把 cash 拆开。

于是每天分为三个状态:hold,sold,rest。

hold[i]表示在第i天必须持有股票时的最大收益； sold[i]表示在第i天当天操作卖出股票且不持有股票的最大收益； rest[i]表示在第i天不操作且没有股票，它可以是cooldown，也就是由于之前一天卖出股票，今天不能买，没有股票的状态， 或者是之前的某天卖出了股票，今天不操作且没有股票；

得到三个方程： (1) hold[i] = max(rest[i-1] - prices[i], hold[i-1]) // 昨天(第i-1天)已经持有股票，那直接过来；昨天没持有股票，那必须是昨天没有操作的过来，今天买变成持有状态 (2) sold[i] = hold[i-1] + prices[i] // 今天必须卖，那么前提是昨天必须持有 (3) rest[i] = max(sold[i-1], rest[i-1]) // 今天不操作且没有股票，那昨天也不能有股票，从rest或者sold两种没持有的情况过来

答案在最后一天，当然状态不可能是hold，是sold和rest中最大的那个。

现在考虑三种状态的初始情况。第一天hold[0]=-prices[0],sold[0]= INT_MIN,rest[0]=0,因为第一天要是hold必须通过买进，消耗了prices[0]；无法卖出，所以初始化为负利润。

也可以进一步优化，把空间复杂度降到O(1)，只用三个变量滚动即可。但滚动的写法有个坑，必须注意。

滚动时必须先存旧值（本题就地更新会算错）

推荐写法是：开头先把所有旧值存成 prev，之后右边一律只读 prev，左边直接写回原变量：

int prevHold = hold, prevSold = sold, prevRest = rest;
hold = Math.max(prevHold, prevRest - price);
sold = prevHold + price;
rest = Math.max(prevRest, prevSold);

右边清一色 prev，严格对应递推式「新值只由旧值决定」，结构上就不可能出错。

如果贪图省事直接就地更新：

hold = Math.max(hold, rest - price);
sold = hold + price;          // 用到的是刚更新过的 hold
rest = Math.max(rest, sold);  // ★ 用到的是刚更新过的 sold —— 这里出事

rest = max(rest, sold_新) 的含义变成了「今天卖出，今天就已经熬过冷冻期」，冷冻期被整个跳过。

反例 prices = [1, 2, 3, 0, 2]，正确答案 3：

算出 4，比正确答案多 1。那 1 块钱来自非法排程：第 2 天卖（价 3）、第 3 天买（价 0），中间没隔天。

为什么别的股票题就地更新却没事：判据不是「有没有被覆盖」，而是「覆盖引入的那一项对应什么动作」。

通用原则：状态数 >= 3、或转移之间有依赖顺序时，一律先存 prev，不要就地滚。就地滚只在「能一眼看出多算的那一项无害」时才值得（比如两状态的 122）。309 正是超过这条线的第一道题——三个状态、两处依赖旧值，就地写法的正确性已经不是一眼可见的了。

这类判断和背包降维选正序／倒序是同一回事：都在问「用新值会让哪条非法路径变得可达」。

714. Best Time to Buy and Sell Stock with Transaction Fee

题意：此题与309不同之处在于，不需要冷冻，但是每次购卖的时候需要交交易费。题目要求在买之前必须卖，也就是说买卖股票一定是交替的，不能连买两次。

解：本题属于股票系列里「只改转移式、不加状态」那一类（总纲见《总结（一）》121 题）——它就是 122（不限次数）加上卖出扣费，状态数仍然是 2，不像 309 需要拆出第三个状态。

原因是：扣不扣 fee 只取决于「现在是不是在卖」这个当前动作，不依赖任何历史，所以无需把历史编码进状态。

这次的状态只有hold和sold。记住sold时候要考虑fee。

hold[i]的意思是在第i天持有股票的最大利润，sold[i]的意思是在第i天没有持有股票的最大利润。

hold[i] = max (hold[i - 1], sold[i - 1] - prices[i]); // 要么i-1天已经有股票了，今天不能买，直接等于昨天；要么i-1天没有股票，今天买使得处于有股票状态 sold[i] = max (sold[i - 1], hold[i - 1] + prices[i] - fee); // 要么第i-1天已经是没股票了，那么今天不能卖，直接等于昨天；要么昨天有股票，今天卖出使得处于没股票状态，并交费

初始情况： hold[0] = -prices[0]; // 第一天买股票，收益是负的。 sold[0] = 0; // 第一天没有股票，卖出去也是收益0。

结果是sold[size-1]，因为最后一次只能卖出股票，让自己处于sold状态。

678. Valid Parenthesis String

题意：括号匹配，括号只有”()”一种，但是存在*,可以代表’(‘, ‘)’或空。

解：此题解法多样。 方法一：动态规划+记忆化搜索。dp[i][j]表示从下标i到下标j的区间内的串是有效的，还是无效的。

情况1：如果i==j，那么看str[i]是不是等于”*“，如果等于则为true，否则为false。

情况2：如果i和j不等，且i和j之间是相邻的，也就是j-i == 1。我们看s[i]和s[j]是否匹配，看是不是这几种情况：”()”, “*)”, “(*”, “**“，如果都不是，那么返回false，否则返回true。

情况3：如果i和j不等，且i和j之间相差大于1，那么看dp[i][k]和dp[k+1][j]（其中k >= i && k < j）两者是不是为true，如果存在一个都是，则返回true，如果一个都找不到，那么返回false。

此方法时间复杂度是O(n^3)，因为每两个下标都会处理n的时间。属于暴力求解。

方法二：观察下面几种情况：”**”, “*)”, “*(“。我们发现，只有第三种的 “(“是无效的。

使用两个栈，一个栈存储左括号’(‘的下标，另一个栈存储’*‘的下标。这样，扫描时候当遇到’*‘或者’(‘，那么先分别压入对应的栈。遇到右括号时候，尝试匹配，如果失败则返回false。

匹配右括号的时候，先尝试从左括号栈进行弹出，因为在两个栈都存在元素时候，情况无非是”*(“、”(*“，其中无论哪一种情况，都可以使用’(‘和当前’)’进行匹配消除，因为*可以作为空来看。如果是left栈没有，那么使用star栈的*来抵消，如果star栈也没有，说明匹配不上，直接返回false。

右括号匹配完了，接下来来分析剩余的左括号和”*“之间的关系是否合法：把剩余的”*“当做“)”或者空来看与左括号进行消除。

最终我们看两个栈的情况，如果left栈顶的值比star栈顶的值大，说明出现了”*(“的情况，也就是说，想消掉此”(“已经不可能了，返回false。

反之，两个栈都弹出值，把剩余的”*“当做“)”，最后我们看左栈是否为空，如果不为空，那么说明消不掉，返回false。否则返回true。如果最后剩余的是star栈，那么无所谓。

10. Regular Expression Matching

题意：给出两个串，一个串s是字母构成的，一个串p是除了字母以外还包含’*‘和’.’的，’.’匹配任意一个字母，’*‘可以表示之前一个字母可以出现0次或者多次 （注意：’*‘之前不能是’*‘，题目给出的输入保证了不会出现这种情况） 。

现在求s和p是否能匹配。s和p的长度不一定相等。

匹配的例子： isMatch(“aa”,”a”) → false

isMatch(“aa”,”aa”) → true

isMatch(“aaa”,”aa”) → false

isMatch(“aa”, “a*”) → true

isMatch(“aa”, “.*”) → true

isMatch(“ab”, “.*”) → true

isMatch(“aab”, “c*a*b”) → true

理解：p串中不存在**这种情况。

解：此题使用动态规划来解。可以列一个表格，纵向为s串，横向为p串。dp[i][j]表示s串中下标0到i的子串和p串中下标0到j的子串之间是否匹配。 那么我们来考虑p[i]和p[j]：

(1) 如果s[i] == p[j]，那么dp[i][j] = dp[i-1][j-1]。

(2) p[j] == ‘.’，虽然p[i]不等于p[j]，但是’.’可以匹配任意一个字母，所以dp[i][j] = dp[i-1][j-1]。

(3) p[j] == ‘*‘，此时看p[j - 1]和s[i]的关系，(a)如果不等，那么dp[i][j] = dp[i][j-2],也就是说我们把j-1处和j处的*一起当作空字符(0次)来处理。

(b) 如果p[j - 1] == s[i]或者p[j - 1] == ‘.’，那么可以是把j-1处和j处的*一起当作空字符来处理, 也就是dp[i][j] = dp[i][j-2]。

也可以是把j-1处和j处的*一起当作两个以上j-1处的字符来处理，此时dp[i][j] = dp[i-1][j]（理解：本质是完全背包，参考518题）。也可以是把j-1处和j处的*一起当作一个j-1处的字符来处理，此时dp[i][j] = dp[i][j-1]。

(4) p[j] != s[i]且p[j]是一个普通字符，此时匹配不上，dp[i][j]=false。

初始化条件是：i = 0的时候，表示s串为空，那么看p串0到pLen的考虑，如果p[j]为’*‘，那么dp[0][j] = dp[0][j - 2]，否则dp[0][j]为false。dp[0][0] = true。

总结：

1. 此题最难的部分在于’*‘的考虑，一开始以为’*‘只是匹配任何s串的最后一个字符或多个字符，其实不然：’*‘一定要结合之前的一个字符来考虑，分两种大情况： 一种是之前一个字符x和s串（当前）最后一个字符可以匹配（例如相等或者之前的字符是’.’），这种又可以分为三种小情况来看，a) ‘*‘当作出现一次，也就是’x’ == ‘x’， b) ‘*‘当作出现多次，也就是’x’ == ‘xxx…‘， c) ‘*‘当作出现0次， ‘x’ = ‘‘； 一种是如果不匹配，那么把’x‘当作空来看，也就是出现0次的情况。

2. 编码难点在于初始情况难想，由于公式中，j依赖于j-2，所以j列的初始化不能仅仅初始化一列，而是要初始化两列，而继续分析，发现j依赖j-2的情况仅仅发生在p[j] == ‘*‘的时候， 而出现’*‘的时候，那至少之前是有两列，所以不需要初始化两列了。。。但是要注意第一行的初始化，例如s{}能匹配p{a,*}这种情况， 具体来说，还是动归思路，当元素为’*‘的时候， 只考虑’*‘当作空来看，也就是dp[0][j] = dp[0][j - 2]。

3. 一个违反直觉的地方：s串并不比p串长，相反，由于’*‘当作出现0次，p串可以比s串长。在二维的dp的时候，习惯性的把短的作纵坐标（数组第一维度）。

44. Wildcard Matching

题意：此题和第10题区别在于使用’?’来匹配任意字符，不是使用’*‘扩充任何前缀字符，而是作为任意长度的某个字符的串，也可以为空。结果必须是完全匹配的。”aab”, “c*a*b”在第10题中是true的，但是此时为false，因为*不能消除之前的c字符。另外*并不是扩充之前的字符，而是可以是任意字符。 isMatch(“aa”,”a”) → false

isMatch(“aa”,”aa”) → true

isMatch(“aaa”,”aa”) → false

isMatch(“aa”, “*”) → true

isMatch(“aa”, “a*”) → true

isMatch(“ab”, “?*”) → true

isMatch(“aab”, “c*a*b”) → false

解：方法与第10题是相同的。先看s[i]和p[j]，如果相等，那么dp[i][j] = dp[i-1][j-1]，

如果不等，但是p[j] == ‘?’，那么也是dp[i][j] = dp[i-1][j-1]。

如果p[j] == ‘*‘，那么，可以把*看做是空，此时dp[i][j] = dp[i][j-1]。

也可以把*当作等于s[i]，此时dp[i][j] = dp[i-1][j-1]。

也可以把*看做两个（多个）s[i]，尽管s[i- 1]可能不等于p[i - 1]，因为*可以匹配任何串，此时p[i][j] = dp[i-1][j]（理解参考518完全背包）。

689. Maximum Sum of 3 Non-Overlapping Subarrays

题意：给出一个数组和整数k，找出三段互不重叠、每段长度恰好为k的连续子数组，使三段之和最大。

返回的是这三段的起始下标（长度 3 的数组），不是和。另外如果有多个答案，要返回字典序最小的那一个——这一条会直接影响代码里比较用 > 还是 >=。

解：核心思路是枚举中间那一段，左右各取预先算好的最优。

三段互不重叠，一旦固定中间段的起点 m（该段是 [m, m+k-1]），那么：

左段必须整段落在 m 左边  →  起点 <= m - k
右段必须整段落在 m 右边  →  起点 >= m + k

所以只要预先算好「左边某范围内最好的一段在哪」和「右边某范围内最好的一段在哪」，枚举 m 就能 O(1) 拼出答案。

不变量（注意两个数组存的都是起点，不是终点）：

sum[i]   = nums[i] + ... + nums[i+k-1]                i 的范围是 [0, n-k]
left[i]  = 在 [0, i]   这段范围里，和最大的那个窗口的【起点】
right[i] = 在 [i, n-k] 这段范围里，和最大的那个窗口的【起点】

第一步：滑动窗口 O(n) 算出 sum 数组。

第二步：正向扫算 left。

left[0] = 0;
for (int i = 1; i <= n-k; i++)
    left[i] = (sum[i] > sum[left[i-1]]) ? i : left[i-1];

第三步：反向扫算 right。

right[n-k] = n-k;
for (int i = n-k-1; i >= 0; i--)
    right[i] = (sum[i] >= sum[right[i+1]]) ? i : right[i+1];

注意两个不等号方向相反，这正是「字典序最小」落到代码上的地方：

方向相反，但目标一致——都是让留下的那个下标尽可能小。

第四步：枚举中间段的起点。

for (int m = k; m <= n - 2*k; m++) {
    int l = left[m-k], r = right[m+k];
    int total = sum[l] + sum[m] + sum[r];
    if (total > best) { best = total; ans = new int[]{l, m, r}; }
}

m 的范围是 [k, n-2k]（这是一个连续范围，不是「只能取 k 或 n-2k」）：左边要放得下一整段所以 m >= k；右边要放得下一整段所以 m + k <= n - k，即 m <= n - 2k。

这里必须是 left[m-k]，不能写成 left[m-1]。因为左段是 [s, s+k-1]，要完全在中间段左边就得满足 s + k - 1 < m，即 s <= m - k。写成 m-1 会让左段和中段重叠。

第四步的 > 也是为字典序服务：m 从小到大枚举，用严格大于就保证了平手时留下更早出现（即 m 更小）的那组答案。

跑一遍例子 nums = [1,2,1,2,6,7,5,1], k = 2，此时 sum = [3, 3, 3, 8, 13, 12, 6]：

答案 [0, 3, 5]。

时间 O(n)，空间 O(n)。

265. Paint House II

题意：n个房子，k种颜色，cost[n][k]矩阵表示为某个房子上第k种色的代价。求给全部房子上色的最小代价，且房子之间不能涂一个颜色。

解：此题区别于I的是有k种颜色，但是当前选颜色时候，只需要考虑之前两个最小值就可以了。

对每一个房子每一种颜色进行考虑，当前房子上色时候，看最小代价和颜色，次小代价颜色，

记录之前房子最小代价以及对应的颜色和次小代价以及对应的颜色，如果当前选的最小代价颜色和之前最小代价是一个颜色，那么就选次小的，否则选之前代价最小的。

当前层计算时候，也要得出自己的最小值和第二小的值供下一层使用。

PS.此题技巧一个是如何保存上一次的两个变量，另一个是如何更新最小的两个值（技巧就是更新最小值时候要把当前最小值赋值给第二最小值）。

276. Paint Fence

题意：给篱笆上色，n个篱笆，k种颜色。不能出现连续三种同样颜色的房子，求给篱笆上色的种数。

解：此题仍然是动态规划题目。

当只有一个篱笆的时候，篱笆上色有k种；当有两个篱笆的时候，是k*k种选择；

当有三个篱笆呢？由于是连续方式的动态规划，所以考虑以某种性质为结尾的情况，

如果第一二个篱笆颜色一样，那么第三个篱笆有k - 1种选择；

如果第一二个篱笆颜色不一样，那么第三个篱笆有k种选择；

那么，第一二个篱笆颜色一样有多少种呢？k种；第一二个篱笆颜色不一样有多少种呢k * (k - 1)种；

以此类推，考虑第四个篱笆，其实是取决于第二三个篱笆的这两种状态的；

所以，对于第三个篱笆，要分别计算两种情况：二三是同颜色，或二三不同颜色。

以此类推，考虑以第i个篱笆为结尾的子问题。

f(i)代表最后两个颜色是相同的情况；g(i)代表最后两个颜色是不相同的情况。

f(i) 可以从f(i - 1)以及g(i - 1)两种情况完全推导过来： 如果从其中f(i - 1)过来，那么第i个和第i-1个，i-2个同个颜色了，不符合条件，所以过不来； 如果从其中g(i - 1)过来，那么必须保证第i个和第i-1个颜色一样，没得选，所以也是g(i - 1)种； 总结下来：f(i) = g(i - 1)。

g(i) 也是可以从f(i - 1)以及g(i - 1)两种情况完全推导过来： 如果从其中f(i - 1)过来，那么保证第i个和第i-1个颜色不一样即可，存在k-1种选择情况； 如果从其中g(i - 1)过来，那么还是保证第i个和第i-1个颜色不一样即可，存在k-1种选择情况； 总结下来：g(i) = (f(i - 1) + g(i - 1)) * (k - 1)。

最终的结果是两种情况的相加，就是f(i) + g(i)。

再来看初始情况：f(0)，由于之前没有color，所以f(0) = 0； g(0)，之前没有color，可以认为就是不同，所以g(0) = k;

PS.

1. 会超过整数的最大值，所以在公式的合适地方使用 %MOD，具体来说： f(i) = g(i - 1) % MOD； g(i) = (f(i - 1) % MOD + g(i - 1) % MOD) % MOD * (k - 1) % MOD。

2. 进一步使用滚动数组，将空间变为O(1)。

368. Largest Divisible Subset

题意：给出一个装满了正数且不含重复元素的数组，现在求出最大子集，要求这个子集中的两两元素都满足Si % Sj == 0或者 Sj % Si == 0. 例如：1，2，4，8就是满足这种条件。

解：使用动态规划思路，假设dp[i]为最大子集必须以下标i结尾，那么答案一定在某个具体的i上。先从小到大排序，因为这样才能快速考虑比一个元素自己小的所有元素：大余小才有意义。

另外，我们观察1，2，4，8的规律，规律就是，只需要最后一个较小数余为0就可以了，因为4一定包含之前等比的情况，也就是一定比是2的情况。

剩下的一个问题是不仅要知道长度，也要知道具体数字。

解决方法就是，维持一个prev数组，记录最大值是从之前哪个元素更新而来（prev的值随着每次最大值进行更新）。

790. Domino and Tromino Tiling

题意：2xN的矩阵用两种骨牌铺满的情况数。

解：此题是dp，dp题目一定要先列1，2，3，4的基本情况，看递推公式，计算正确的公式是难的，最终编码是简单的。

参考http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-790-domino-and-tromino-tiling/。

https://leetcode.com/problems/domino-and-tromino-tiling/discuss/116581/Detail-and-explanation-of-O(n)-solution-why-dpn2*dn-1+dpn-3

还是按照骨牌有突出来理解比较好。这么理解的本质还是递归，把问题末尾填上几种不同情况，那么问题的规模就会缩减。

dp[i][j]表示长度为i（两行长度最小值），末尾形状为j的拼接方法总数，j = 0表示末尾没有多余部分，j=1表示第一行突出一个，j=2表示第二行突出一个。那么推导公式为：

dp[i][0] = dp[i - 1][0] + dp[i - 2][1] + dp[i - 2][2] + dp[i - 2][0]

dp[i][1] = dp[i - 1][0] + dp[i -1][2]

dp[i][2] = dp[i - 1][0] + dp[i -1][1]

注意计算起始值: 如果是按突出那一列i的来算，那么起始值是dp1[1] = dp2[1] =dp3[1] = 1; dp1[2] = dp2[2] = dp3[2] = 2。等于2的意思是，要么是三角的自己，要么是一个横的。

如果是按突出一列的前面一列来算，就是dp1[0] = dp1[1] = dp2[1] = dp3[1] = 1。

474. Ones and Zeroes

题意：给出一个0，1串的数组，然后给出总的0，1数，问最多可以构造数组中多少个串（有消耗）。例如{“10”， “0”， “1”}, 给出1的个数m=1， 0的个数n=1。虽然1个1，1个0可以构造出其中任何一个串，但是在有消耗的情况下，构造出后面的 “0”， “1”是最优选择，也就是可以构造出两个串。

解：此题两种思路：

一种是dfs，相当于是计算子集的题目：对于数组中一个元素，有选和不选两种情况，这样只要dfs回溯的搜索一遍，就可以得出答案。

一种是dp，就是从物品集合中01的选出若干物品，来满足一定的要求。由于此题不要求计算具体路径，所以使用dp。

此题独特之处，就是一种三维的dp，第一维以下标k结尾的集合，第二维m，第三维n。dp[k][i][j] 表示k,i,j三个维度消耗的最多子串。每次考虑新加入一个可选项k来考虑进一步规模的问题， 考虑选择第k项，以及不选第k项，不选第k项就是等价于dp[k - 1][i][j]，选择第k项，那么就是等价于dp[k - 1][i - k包含的0][j - k包含的1] + 1，加1的原因是此处多了一种匹配，也就是 当前第k项的匹配，考虑第k项的最终结果是二者（选或不选）中的较大者。注意一个细节，如果i - k包含的0或者j - k包含的1不合法，那么dp[k][i][j]要等于dp[k - 1][i][j]， 而不是0。

可以使用滚动数组在空间上进行优化（从N^3到N^2）。原理是k,i,j只依赖于k-1层和k层的结果，只需要记录二维的i，j信息即可，不过要注意依赖的是之前层的较小下标，因此循环的时候，下标要 从大到小计算，这样才不会破坏依赖的较小下标。

总结：如果不求具体路径，使用dp的是最好的，因为自底向上可以避免大量的重复计算。

808. Soup Servings

题意：给出初始值对(NA, NB)，有给出的四种方式s1(4, 0), s2(3, 1), s3(2, 2), s4(1 ,3)等概率来消耗原始值，现在求NA先消耗掉的概率。

解：此题是动态规划，因为递归情况存在大量重复。dp[i][j]代表i，j时候i先消耗掉的概率，那么等于0.25 * dp[i - 4][j] + 0.25 * dp[i - 3][j - 1] + 0.25 * dp[i - 2][j - 2]

• dp[i - 1][j - 3]。

再考虑基本情况：dp[0][0] = 0.5。因为同时消耗到0的概率是50%。dp[0][j] = 1 (j > 0的情况下) i < 0, j < 0的情况，同时小于0的情况等价于同时等于0，也就是50%，等价于i，j同时为0； i > 0, j < 0 的情况，概率是0，等价于i > 0, j = 0的情况。

此题要根据25做等比例修改，一个公式是(N - 1) / 25 + 1 或 (N + 24) / 25。

此题还有个最坑的点就是N很大的时候，内存却有限制。所以网上的解都是在N大于一定数的时候，数学上分析大概率99.99%是A先消耗完，直接返回1了。。

375. Guess Number Higher or Lower II

题意：给出一个1到n的数，然后让你猜，每次会告诉猜高了还是猜低了，不过每次猜错都要支付猜的那么多钱，现在问要支付最少多少钱可以一定猜的到该数。

「最少多少钱可以保证……」怎么理解：这句话里套了两层，拆开就好懂。

生活类比：出门旅行要带多少现金？你问的不是「平均要花多少」，而是「带多少才能保证不管发生什么都够用」——那就得按最倒霉的情况算。但你可以选路线：走 A 最倒霉要 500，走 B 最倒霉只要 300，那你选 B、带 300。所以「最少的钱保证够用」= 在所有走法里，挑一个最倒霉时花费最低的，那个最倒霉的花费就是答案。

放到本题：把「答案」想成一个故意坑你的人。他心里没有提前定好数字，你每猜一次，他就挑让你更花钱的那个回答（只要不和之前说过的矛盾）。问的是：你最少准备多少钱，才能不管他怎么坑都猜得中。

以 n = 4 为例：

• 第一次猜 2：他若说「高了」（答案是 1），你付 2，下次必中，共 2；他若说「低了」（答案在 3、4），你付 2，再猜 3，他又说「低了」（答案是 4），再付 3，共 5。他当然选后者，所以猜 2 要准备 5 块。
• 第一次猜 3：他若说「低了」（答案是 4），你付 3，共 3；他若说「高了」（答案在 1、2），你付 3，再猜 1，他又说「低了」（答案是 2），再付 1，共 4。他选后者，所以猜 3 只需准备 4 块。

所以第一次该猜 3，答案是 4。

怎么认出是 DP（识别信号）

读题时问三个问题：

1. 问的是最优值吗？ 「最少多少钱」→ 是，候选是 DP 或贪心。
2. 做一个选择后，剩下的问题和原问题是同一种吗？ 猜了 x 没中 → 答案在 [i, x-1] 或 [x+1, j] 里，还是「在一个区间里猜数」，只是区间变小了 → 能递归。
3. 能贪心吗？ 贪心就是「每次猜中点」（二分）。但上面 n = 4 已经说明了：猜中点 2 要 5 块，猜偏右的 3 只要 4 块。中点不是最优。

最优值 + 子问题同构 + 不能贪心 → DP。而且子问题是一段连续区间，每次决策是「在区间里挑一个点」，切完还是区间 → 区间 DP。

二分在这里失效的原因：二分优化的是猜的次数，而本题要的是花的钱，而且每次猜的代价取决于猜的是哪个数。选择的代价取决于选择本身时，「均匀切分」的直觉就不成立了。

两层：哪个能控制，哪个不能（这是本题的核心）

猜 x 之后，还是继续在 [i, x-1] 和 [x+1, j] 其中之一里猜，但落到哪一边是自己不能控制的，最坏情况下，对手会把数藏在代价较大的那一侧；而怎么选 x 是自己可以主动掌握的，所以选最有利的那个 x。（2026-10 用户自己的总结）

注意这里的「代价较大的一侧」指的是 dp 值较大的那一侧，不是数值较大的那一侧。两者常常重合，但不总是。还是 n = 4 猜 3 的例子：猜高了答案在 [1, 2]，还要花 dp[1][2] = 1；猜低了答案在 [4]，还要花 dp[4][4] = 0。对手会把数藏在左边 [1, 2]——数值更小，但区间更长、还得再猜一次，所以代价更大。

解：此题一开始陷入二分搜索的思路，但是很明显，二分只是一种方法，而不是总体思考解决这个问题。此题其实是动态规划题。

不变量：

dp[i][j] = 已知答案一定落在 [i, j] 内时，保证猜中所需的最少钱

「已知答案落在 [i, j] 内」这个前提不能省——正是它保证了猜 x 错了之后，答案只可能在左半或右半，所以才是两者取最坏。

这个不变量是规则「发的牌」，不是自己挣来的。开局时答案在 [1, n] 是题目给的；之后每一次「高了／低了」的回答，都在缩小区间的同时替你维护着「答案仍在区间内」。DP 只是踩在这张牌上。

而这张牌能一直成立，靠的是一条规则：对手能坑你，但不能骗你。

• 坑 = 在合法的两边里挑更贵的那一边 —— 允许，这就是公式里的 max
• 骗 = 说假话、和自己之前的回答矛盾 —— 不允许

不变量依赖的正是「不能骗」。对手再恶意，也必须前后一致，所以答案永远留在当前区间里。如果允许对手撒一次谎（真实存在的变体，「带谎言的二十问」），一次「高了」之后答案未必在左边，[i, j] 这个不变量当场失效，干净的区间 DP 就塌了——状态里得额外记「他还剩几次谎可以撒」。

这和二分查找是同一张牌。lower_bound 的不变量是「所有 i < left 都有 a[i] < x，所有 i >= right 都有 a[i] >= x」，说到底也是「答案恒在当前区间内」。区别只在于谁来保证它：

那么如果猜x，x是介于i到j的数，那么需要花 x + max(dp[i][x-1], dp[x+1][j]) 的钱。

最终公式：

dp[i][j] = min over x in [i, j] of  ( x + max(dp[i][x-1], dp[x+1][j]) )
           ↑                              ↑
        我挑猜哪个 x（能控制）      对手挑往哪边走（不能控制）

• max：猜 x 之后落在哪边我控制不了，所以按最坏算，也就是假设每次都猜错、且被带到更贵的那一边。
• min：猜哪个 x 是我决定的，所以在所有 x 里挑最好的。

这种「我选最好、对手选最坏」的结构叫 minimax，和 486 取数博弈是同一种结构——486 外层 max 是我、内层 min 是对手；本题外层 min 是我、内层 max 是对手。方向相反，只因为 486 求「我拿最多」、本题求「我花最少」。

初始条件：i == j的时候，dp[i][j] = 0；因为猜对了是不支付的！

i > j的时候（公式里面的max (dp[i][x - 1], dp[x + 1][j])很容易出现这种情况），公式里面的该项就当作不存在（当0处理）。

代价的本质：一棵决策树上最重的那条路径

把猜数过程画成一棵树：每猜一个数是一个节点，猜错了往左或往右走，走到答案为止。路上所有猜错节点的数值之和就是这个答案的花费，而「保证猜中」所需的钱 = 所有路径里最重的那一条。

     猜中点 2                    猜 3
        2                         3
       / \                       / \
      1   3                     1   4
           \                     \
            4                     2

  最重路径 2 → 3 → (4)       最重路径 3 → 1 → (2)
  权重 2 + 3 = 5             权重 3 + 1 = 4

二分查找也是一棵树，但它的每个节点权重都是 1（猜一次算一次），所以优化的是路径的节点数，最优形状是根在中点、左右按数量平衡。本题每个节点的权重是猜的那个数，优化的是路径的权重和，所以要按权重平衡——贵的那边要浅，便宜的那边可以深，根自然偏右。

这其实是「等权则贪心，带权则 DP」的又一个实例（同 435 与 1235）：每次猜算 1 次 → 二分；每次猜付 x 元 → DP。

两个支柱与两个顺序

DP 之所以成立：一是最优子结构——大区间的最优树可以用小区间的最优树拼出来（若某子树不是最优，换成那个区间的最优树，最坏路径只会变轻或不变）；二是自底向上——先把所有小区间的最优树造好，大区间只需挑根，挑根时左右两棵已是现成的最优树，只需要它们的代价这一个数。

容易绕晕的是两个顺序正好相反：

根是最先猜的，却是最后算出来的。

顺带和 312 对照：本题挑的是「第一个猜的 x」，312 挑的是「最后一个戳的 k」，时间顺序完全相反，但在区间 DP 里扮演同一个角色——把区间切开、让左右两段成为互不干扰的独立子问题的那个点。区间 DP 的关键不是先做还是后做，而是找到那个能把问题切成独立两半的点。

PS. 使用记忆化搜索就可以计算出结果。本题是最优二叉搜索树（Optimal BST，给定访问频率求期望查找代价最小的 BST）的最坏情况版本。若把题目改成「平均要花多少钱」，只需把内层的 max 换成按概率加权求平均，结构完全不变。

813. Largest Sum of Averages

题意：将数组分为k份，顺序不变，求使得每段平均数和最大为多少。

解：此题是动态规划，考虑其中的子问题，一种是(i, j)数组分成x份，这就是三维动态规划dp[i][j][k]；或者是(0, i)数组分成x份。

此题只需要二维dp[i][x]就可以，因为如果分为三维，那么会出现重复考虑，例如前面一段分一段，后面一段分两段实际上和前面一段分两段后面一段分一段是等价的情况。

所以，dp[i][x]表示0到下标i切成x段的最大平均和，其中要求i要小于等于x，否则就是切分不了x份，当作边界情况0。

基本情况，dp[i][1]的意思就是切成一份，也就是数组和。dp[i][2]的意思是，以0到i为分界点划分成两份的结果。

dp[i][k]与dp[i][k - 1]的关系，也就是在0到i中在找一个分界点j，把0-j的部分看成是dp[j][k - 1]，剩余的部分看作是一份。 也就是dp[i][k] = max { dp[x][k - 1] + sum(x, i) / i - x}, 0 < x < i。

继续看基本情况：dp[0][0] = 0，dp[0][1] = nums[0]，dp[0][i] = sum(0, i) / i。

计算顺序，k紧紧依赖前一列，i依赖前面几行。因此，在循环的时候，一定遵照小下标先计算，也就是从小到大循环。

时间复杂度O(N^3)。

294. Flip Game II

题意：两个人每人一步翻转连续的++为–，直到对手没得选，自己就赢了。

解：此题一开始总觉得在自己可选的几个选项中也许有最佳的选择，然后考虑对手选择之后的在选。

实际上应该这么考虑：自己先手时候把每一步可能的都走一遍，走完之后，对手也是相同策略，也是先手的获胜，那么只要自己走的所有可能情况中只要有一种是对手先手是失败了，那自己就一定能成功。

所以此题是dfs回溯加上记录中间结果。

PS. 和下棋一样，如果说棋局落入下风了，实际上的意思是，已经看到先手的失败了。

562. Longest Line of Consecutive One in Matrix

题意：求矩阵中上下、双对角线连续的最长的1。

解：使用三维动态规划，dp[i][j][4]表示，下标i，j为结尾的最长的连续的1。每个格子只依赖前面的格子，如果为1，那么加1，否则是0。

使用常规的自上而下，从左到右的扫描，因为dp[i][j][4]只依赖左边，上边，左上边，右上边的格子。

361. Bomb Enemy

题意：给出二维矩阵，0的地方可以放入炸弹，炸弹可以炸所在行和列（但是不能越过墙），W表示墙，E表示敌人，所以题目问的是在哪个0放入炸弹可以炸最多的敌人。

解：此题就是暴力求解，

方法一：准备4个二维数组，分别表示该位置上下左右分别有多少个E。然后，正着扫描一遍二维数组，根据左和上的信息更新当前信息。倒着扫描一遍二维数组，根据下和右的信息更新当前信息。然后在扫描一遍，把0所在的地方上下左右结果加起来就是当前坐标可以消灭的E数，扫描完就知道是哪个坐标可以消灭最多E。PS.正反扫描时候，会出现越界问题，第一行，第一列，最后一行，最后一列都要单独处理。

PS.核心计算就是计算当前位置左侧（右、上、下）到当前位置为止有多少个字符‘E’。

552. Student Attendance Record II

题意：第I题是验证是否可以得奖，此题是只给出串的长度n，要求把所有可以得奖的情况列出来，得奖的情况就是串没有多余一个的A，也不能出现连续的三个L。

解：此题有一种非常巧妙的动态规划解法：将A和非A单独考虑，那么我们发现，对于长度为k的问题来说，A由于不超过一个，那么如果选A，那么A可以出现在任何一个位置，剩余的部分就是两个非A的情况，另外如果不选A，那么整个串就是非A的情况。

再来考虑非A的情况，非A的情况下，就是一维dp，考虑结尾，如果是以P结尾，那么dp[i] = dp[i - 1]；如果以L结尾，那么要看之前是什么结尾，发现只有LLL这种结尾是不合法以外，其余结尾都满足dp[i] = dp[i - 1]的需求，所以我们得出递归公式是dp[i] = 2 * dp[i - 1] - dp[i - 4]。

再来考虑边界情况：如果n比4小，那么就需要直接计算了，由于前4个都是直接计算的，因此在一开始申请数组的时候，如果n比4小，那么至少要分配4个空格。

另外一个问题是结果太大要模M，那么在c++的时候，对负数求模，要先让负数加一个M，然后在使用%来模M。

568. Maximum Vacation Days

题意：给出nxn矩阵flight表示城市i到j的是否有航班，也就是城市路线图的邻接矩阵，然后又给出nxk矩阵days，表示城市i可以在第j周休息多少天的邻接矩阵，现在要求最大可以休息多少天。 第一天必须从城市0出发，一共有k周。

解：此题是动态规划解的题，但是总的思路似乎可以使用不带visited数组的dfs（泛洪？？），从第i个城市出发，下一个城市可选的范围是它的邻居，然后当前对应的层就是所在的周，然后从全部的最后一周的结果选最小的那个，就是答案。此题的意思似乎不是每个城市只能待一次，而是条件允许可以待多次。这样纯dfs的时间复杂度是n ^ k。

画一个搜索树图就知道，下面的层中存在大量重复，重复就是指，第j周出现在第i个城市这种相同分支。

所以，一个方法是使用记忆化搜索，使用dp[i][j]来记录已经搜索过的结果，表示有j周从城市i出发能休假的最多天数，这样能减少大量重复。

再来看自底向上的解法。相比于自顶向下，该方法的好处是，可以使用滚动数组来使得空间复杂度降低到O(n)。来看下递推公式：dp[i][j] = max (dp[i - 1][x] + days[j][i]),其中x介于0到n-1，且可以从城市x到城市j。

其中的i，j与之前定义相反，i表示周，j表示城市，i从k开始到1（反过来的原因是之前结果是不能重复累加的，也就是说如果从1到k，那么之前的值会被累加起来，实际上是不需要的），对于每一周遍历一遍所有航线，看能不能更新dp[i][j]。由于i只与i-1有关，所以可以使用滚动数组来优化空间。

72. Edit Distance

题意：通过增加一个字符，减少一个字符，修改一个字符把串s变成串p，请问最少需要多少步。

解：dp[i][j]表示s.substr(0, i)到p.substr(0, j)的最小步骤，“到”的意思就是说将串s.substr(0, i)变为串p.substr(0, j)。列出二维矩阵，每个格子只依赖与左上角，左，上的三个格子。

583. Delete Operation for Two Strings

题意：给出串S和T，允许删单词，求最少的删除步数，使得两串相等。

解：

思路一：此题和求两个串的公共子序列本质是一样的，只需要先使用dp求出公共子序列长度，在将两串总长度减去该值,在乘以2得出答案。dp[i][j]表示第一个串i结尾与第二个串j结尾的公共子序列，这样我们知道，如果s[i]==p[j]，那么dp[i][j] = dp[i - 1][j - 1] + 1，否则dp[i][j] = max (dp[i-1][j], dp[i][j -1])。

思路二：此题和72 Edit Distance题解题方法一样，只不过只有一种删除操作。

注意的是：如果word1[i - 1] != word2[i - 2]时候，dp[i][j]仍然可以从dp[i - 1][j - 1]推导：也就是dp[i][j] = dp[i - 1][j - 1] + 2。

486. Predict the Winner

题意：给出正整数数组，总和不大于int表示范围，现在两个人从里面取数字，但只能从数组剩余的开头或者结尾取，最后取出总数最大的那个人获胜。现在问先手能不能一定赢。

解：博弈类dp，难点在于如何定义dp[i][j]，例如定义dp[i][j]表示从区间[i, j]里玩游戏时候，先手能取出来的数字总和，这样只要dp[0][n-1]最终大于等于总和的一半，那么就算获胜（题目规定平局也算先手赢，所以是 >=，写成严格大于会把平局判错）。

自己在一开始两种中做出选择之后，变成了对方先手， 所以依赖的dp[i - 1][j]和dp[i][j - 1]是对手先手得出的结果。因此根据直觉，公式是：

dp[i][j] = max {dp[i + 1][j] + nums[i], dp[i][j - 1] + nums[j]}

但是这个直觉来的公式是不对的。

原因是dp[i + 1][j]和dp[i][j - 1]是对手先手，不是自己先手。那来具体看对于对手先选时候dp[i + 1][j]意味着什么（dp[i][j - 1]同理）， 意味着对手的选择被限制在nums[i + 1]和nums[j]里面， 这时候，对手如果选择了nums[i + 1]，那么剩下的dp[i + 2][j]，注意其实里面dp[i + 2][j]里面是可以选到nums[j]的，其实就是把选nums[j]的权力让给我； 同理，对手如果选择了nums[j]，那么剩下的dp[i + 1][j - 1]里面可以选到nums[i + 1]，就是把选nums[i + 1]的权力让给我； 注意无论选了哪个，这个数被对手选去了，自己选不到的！！！

就是dp[i + 1][j] 转换成dp[i + 2][j]，dp[i + 1][j - 1]两个子问题，但又变成自己先手了：就是自己能选到的！ 那么是选dp[i + 1][j]还是dp[i + 2][j]呢？这个取决于对手，对手当然不会让自己能选到大的！

这样，对手怎么达到最优呢？为什么就是选dp[i + 2][j]，dp[i + 1][j - 1]中间较小的？而不是自己选个较大的数，同时也给一个较大的子问题给我们选？ 理解：要从全局问题得解决来考虑，计算我的结果其中一部分子问题肯定会落入到dp[i + 2][j]，dp[i + 1][j - 1]二选一，这种情况下，对手不会让我选到较大的。 就像下棋一样，无论对手这一步走的是什么看起来很怪的棋，其实目的（最优解）都是在给我下一步的局面（子问题）中留下对我最不利的。

也就是说，dp[i][j] = min { dp[i + 2][j], dp[i + 1][j - 1] } + nums[i]

在自己先手的两种子情况下，当然会选最优解，得到最终公式： dp[i][j] = max { min {dp[i + 2][j]，dp[i + 1][j - 1]} + nums[i] , min {dp[i + 1][j - 1], dp[i][j - 2]} + nums[j] }

基本情况：i == j时候，dp[i][j] = nums[i]。i > j的时候，dp[i][j] = 0。

PS.如果是数组包含的元素是偶数个，那么先手一定获胜，只要把奇数位和偶数位的和算一遍，按照较大的走就会赢，因为总能取到所有奇数位或者所有偶数位。

博弈类dp特点就是，第一层结果不直接和第二层发生关联，而是和第三层的发生关联，且第二层可以决定第三层的走向（第三层的结果虽然是自己先手，但是对手可以选择让自己选最差的） 因此，在第三层里面必须全胜（只能选到最差的），败一个都不行，在第二层中只要一个胜利（或者选最大的）就可以胜利。

画博弈树的时候，第三层最好是base case，这样输赢一目了然。

三种思路对照：难点都在「先手会翻转」

本题的根本难点是：dp[i][j] 说的是「站在 [i,j] 这个局面上的先手」能拿多少。我在 [i,j] 取走 nums[i] 之后，局面变成 [i+1,j]，但先手变成了对手——所以 dp[i+1][j] 是对手的分，不是我的。这也正是上面那个”直觉公式”错的原因。

我真正要的是「我在 [i+1,j] 里能拿多少」，它等于 sum(i+1..j) − dp[i+1][j]。围绕怎么拿到这个量，有三条路：

思路 A（本文采用）：不引入 sum，跨过对手那一层

不变量：dp[i][j] = 先手在 [i,j] 上能取到的总分。

既然 dp[i+1][j] 是对手的分用不了，就再往下看一层——等对手走完、又轮到我当先手时，就能用 dp 了。对手会在取头／取尾中挑让我分少的那个，所以取 min：

dp[i][j] = max { min{ dp[i+2][j],   dp[i+1][j-1] } + nums[i],     // 我取头
                 min{ dp[i+1][j-1], dp[i][j-2]   } + nums[j] }    // 我取尾
答案：2 * dp[0][n-1] >= 总和

结构是 max 套 min：外层 max 是我的选择，内层 min 是对手的选择。优点是博弈的两层结构一目了然，代价是要看三个子状态（两步前瞻）。

思路 B：引入前缀和，一步前瞻

不变量同 A，但直接用「总和减对手」算出我的部分：

dp[i][j] = max( nums[i] + sum(i+1..j) − dp[i+1][j],
                nums[j] + sum(i..j-1) − dp[i][j-1] )
答案：2 * dp[0][n-1] >= 总和

只看两个子状态，代价是要多维护一个前缀和数组。本质上就是把 A 里「跨一层取 min」那一步，换成了「用总和减掉对手的最优」——对手的最优已经替我考虑过”他会让我少拿”这件事了。

思路 C：换不变量为「净胜分」

dp[i][j] = 先手在 [i,j] 上的净胜分（先手得分 − 后手得分）
dp[i][j] = max( nums[i] − dp[i+1][j],  nums[j] − dp[i][j-1] )
答案：dp[0][n-1] >= 0

我取走 nums[i] 后，对手在 [i+1,j] 上的净胜分是 dp[i+1][j]，从我的视角看就是我的净负分，所以取反。「先手翻转」这件事被压缩成了一个负号，不需要 sum，也不需要跨层。

能这样做的原因是：净胜分是反对称的——换个人看只变号；而总分换个人看要用 sum − x 才能换算。所以净胜分天然适配”角色轮流翻转”的结构。

三者都正确。A 最贴近”我选 max、对手选 min”的直觉，C 最短，B 介于两者之间。其他博弈题（877 Stone Game、1140 Stone Game II、1406 Stone Game III 等）同样可以用这三种视角去看，届时再比较哪种更顺手。

312. Burst Balloons

题意：给一个数组，里面是气球，打爆一个气球可以得到左边气球和当前气球以及右边气球的乘积，打完之后临近气球自动变化，求能打出的总和最大多少。两侧边界部分默认算1。

不变量（这题全部的难点都在这一句）

dp[i][j] = 把下标 i 到 j 之间的气球【全部戳破】所能得到的最大金币，
           且计算时以 nums[i-1] 和 nums[j+1] 作为左右两道【不会被戳破的墙】

两个要点，缺一个就写不对：

1. 区间外的 i-1 和 j+1 是「墙」——在这个子问题里它们始终存在、不参与被戳破。所以子问题不是「孤立的一段」，而是「一段 + 两堵墙」。
2. 枚举的 k 是「最后一个被戳破的」，不是第一个。这样 k 被戳时，i..j 里其他气球都已消失，它紧贴的就是那两堵墙，得分固定为 nums[i-1] * nums[k] * nums[j+1]；而 k 左右两段互不影响，可以独立成为子问题。

解： 问题显然要分治，这里如果是当作一个下标结尾的dp[i]子数组看，发现不能解决问题，解空间不够覆盖住信息，所以进一步升级解空间维度，一维到二维： 定义dp[i][j]是下标i到下标j的子数组问题，dp[0][n - 1]为问题答案。

对于整个数组来看，如果选择一个中间气球k来分割为dp[i][k - 1]，dp[k + 1][j]，那么它们和dp[i][j]有什么关系？

自然方向想的话，就是先打爆一个气球k后得到nums[k - 1] * nums[k] * nums[k + 1]，后看剩余的子问题： 也就是dp[i][j] = max{ nums[k - 1] * nums[k] * nums[k + 1] + dp[i][k - 1] + dp[k + 1][j] } ，其中k的范围是i到j。 看起来似乎没有问题，但是实际上这个是错误的！原因就是，第一个打爆k气球之后，dp[i][k - 1]其实无法计算，因为它的右边界不是我们以为的nums[k - 1]或者nums[k]！它的右边界 可能是nums[k + 1]到nums[j]里面的任意一个！同理，我们无法计算dp[k + 1][j]。

那么，dp[i][k - 1]，dp[k + 1][j]到底和dp[i][j]有什么关系？ 如果是先解决子问题dp[i][k - 1]和dp[k + 1][j]呢？也就是说，保留中间气球k作为这两个问题的边界！这意味着我们其实需要把k当作最后一个被打爆的气球！

最后打爆k的时候，如何计算乘积呢？乘积结果一定是nums[k]吗？不一定！这里就是最难想到的一点。 因为i到k-1，以及k+1到j里面的气球虽然在k打爆之前先被打爆了，但是并不意味着k被打爆时候的两个边界都是1！这很违反直觉！ 例如{0，1，2，3，4，5，6}，在计算dp[1][5]的子问题的时候，它的边界其实是0和6！如果k = 3当作解决dp[1][5]的最后一步，那么3最后应该和nums[0]，nums[6]相乘。 那为什么不说0和6这两个地方的气球可能也被先打爆了呢？这还是取决于全局问题如何转换为子问题，单独从子问题dp[i][j]定义来看，就是以i-1和j+1为边界，把其中的气球全部打爆的最优解。

所以乘积是nums[i - 1] * nums[k] * nums[j + 1] !!!

我们知道，最终结果一定落入到k（i <= k <= j）种情况之一，也就是有：

dp[i][j] = max { dp[i][k - 1] + nums[i - 1] * nums[k] * nums[j + 1] + dp[k + 1][j] }，其中 i <= k <= j

注意中间那一项是 nums[i-1] * nums[k] * nums[j+1]，三个下标分别是 i-1、k、j+1：

• k 是最后被戳破的那个气球本身
• i-1 和 j+1 是子问题的两道墙，不是 k 的原始邻居。因为 i..j 里除 k 以外的气球都已经先被戳掉了，此刻 k 左右紧贴着的正是区间外的那两堵墙

这一项最容易写成 nums[k-1] * nums[k] * nums[k+1]（照搬题目原文的形式），那就错了——那是”第一个戳破 k”的算法，而我们的定义是”最后一个戳破 k”。

从公式知道，其中应该是三重循环，因此时间复杂度：O(n^3)。 但是三重循环的编码，下标很难考虑，因此最好使用dfs + memo。 如果是dp编码，那么思路就是从子问题区间大小为1开始一点点的扩大区间，每一步基于上面以及计算的结果。

其中，最基本的子问题是 dp[x][x]（区间里只剩一个气球）。此时 i = j = k = x，代入上面的公式就是 dp[x][x] = nums[x-1] * nums[x] * nums[x+1]（如果 x-1 或 x+1 越界，当作 1）。

注意这里恰好和题目原文的形式长得一样，是因为 i-1 = x-1、j+1 = x+1，纯属巧合，别因此以为一般情况也是 nums[k-1] * nums[k] * nums[k+1]。

总结：1. 一定要充分理解子问题到底是什么，这个里面子问题dp[i][j]就是以i-1和j+1为边界，把其中的气球全部打爆的最优解，然后来看子问题对于解决整个问题到底有什么帮助（子问题之间的关系，子问题解决的先后次序都很重要）。 举例子，作图来理解子问题，最base的子问题是什么都要考虑清楚，否则很容易想当然。

1. 三重循环求max的dp题目（肉夹馍？），编码优先考虑dfs + memo。

727. Minimum Window Subsequence

题意：给出S串和T串，要求S的子串W，T是W的子序列，求最短的W。

解：暴力解法思路就是：对于每一个和T串开头相同的字符开始到结尾，找最小包含的substring，使用经典双指针法，每次花费O(len(S) + len(T))的时间； 然后取出最短的一个作为答案，但是时间复杂度总的来说还是O(len(S) * (len(S) + len(T) )。

此题其实可以想到是与大串小串之间的公共子序列问题类似，也就是串串之间比较的dp题型。

方法二：用dp来解：dp[i][j]表示串T中0到i的子串T’和S串中0到j串S’作为子问题解的时候，其中T’的匹配上的子串（也就是包含S’作为子序列）的最小起始下标。

这样，在S[i] == T[j]的时候，dp[i][j] = dp[i - 1][j - 1]，问题退化成前一步的结果。

S[i] != T[j]的时候，dp[i][j] = dp[i - 1][j]，此时最后一个字符不等，说明问题可以退化成T不变，S前一步的结果。

如果匹配不上，那么dp[i][j] == -1。

编程时候，比较难考虑的点，一个是初始情况：T串为“”的时候，S串的考虑是：S’串中的子串只有“”才能包含“”，但是正常下标往后取子串总是存在字符的，满足不了“”，所以此时起始下标就是S‘串的末尾下一个位置。

另外一点，就是答案蕴含在所有的dp[i][j]的最后一列，也就是T的长度固定，S变长的所有情况中，选择长度的最小的作为最终的答案。

dp的时间复杂度是O(len(S) * len(T))。

方法三：使用特殊的数据结构，next[i][k]，表示下标i的右手边离的最近的字母k的下标。构建这个数据结构也是dp思路： next[i][k] = next[i + 1][k], if S[i + 1] != k； // 意思是如果i+1处的字符如果不等于k，那么其实i处距离k字符结果完全可以继承i+1处； next[i][k] = i + 1, if S[i + 1] == k。 这样只需要双重循环，i从大到小，26次循环，计算出该数据结构。next[i][k]初始化为-1，表示右侧找不到字符k。

这样，对S串扫描，一旦开头等于T[0]，那么用这个数据结构进行快速计算最短substring，花费O(lenS * lenT)时间。

还可以使用改进的双指针解法，类似于KMP。

471. Encode String with Shortest Length

题意：把字符串压缩成最短的k[encoded_string]形式。

解：动态规划，dp[i][j]表示可以把s中下标i到j压缩成最短的形式（k[encoded_string]或原串）。

然后发现，dp[i][j] = min {dp[i][j], dp[i][x] + dp[x+1][j]}。其中还要与s[i, j]的子串t直接压缩后进行比较，直接压缩的技巧就是在t + t中从第一个位置开始查找t，如果发现只能在中间位置找到，那么说明t不可压缩，否则就说明t是可以压缩的。如果压缩不了，那么看中间切割方式与原串之间哪个长度最小，选小的。

403. Frog Jump

题意：给出石头位置坐标数组（已经按升序排序），青蛙从第一个石头开始（第一个石头坐标规定为0）跳，如果能到达最后一个石头，则表示能过河，返回true。

规则就是青蛙只能落在石头上，而且每次跳之后，下一步只能跳是上一步跳的长度k的k - 1, k + 1或者是k三种距离。青蛙只能向前跳，且第一步青蛙只能跳一步，

也就是说，一开始默认之前是通过0跳过来的。

解：采取动态规划思路。

首先确定两个维度，一个维度是所有位置i（先不看石头的具体所在位置，而是扩展成一个空间），

另一个维度是在这个位置上，所有的上一步跳过来的长度j。

要知道，一个位置i，它的所有的信息量都是从它之前的位置信息来的，那么是不是只是依靠位置i-1呢？不是的，

它需要依靠i减去之前跳过来的长度。以具体的（i，j）来说，就是可以从j-1，j，j+1而来，

不变量：

f(i, j) = 能否站在位置 i 上，且【最后一跳的长度恰好是 j】

注意状态里必须带上 j（最后一跳的长度），因为下一跳能跳多远完全取决于它——这就是「能不能做某个动作取决于历史」的典型情形，那段历史必须编码进状态。

转移（逆向看：i 是怎么被跳到的）：

这一跳长度是 j，所以上一个落脚点必然是 i - j，这一点是固定的；变的只是上一跳的长度。若这一跳是 j，那么上一跳的长度 p 必须满足 j ∈ {p-1, p, p+1}，即 p ∈ {j-1, j, j+1}。于是：

三项的第一个下标都是 i - j，不要写成 i-j-1 或 i-j+1。验一下就知道为什么：若写 f(i-j-1, j+1)，它表示”在 i-j-1 落地、上一跳长 j+1”，从那里再跳 j 只能到 i-1，到不了 i；要到 i 得跳 j+1，那算出来的是 f(i, j+1)，不是 f(i, j)。

初始条件是 f(0, 0) = true（起点，尚未跳过，视作上一跳长度为 0，故第一跳只能是 0+1 = 1）。最终答案是看 f(最后一个石头, j) 里是否存在某个 j 为 true。

先看最初的条件是一开始只能跳一步，

从第0步看，就是f(0, 0) = true； 接下来，马上是f（1，1）= true； 然后，就是f（1，0），f（2，1），f（3，2）为true； 这里注意，虽然是i是从小到大计算，但是这里的小的i却可以更新后面大的i。也就是i在计算的时候，i+1和i+2都可以得到更新。 但是计算i的时候，它的所有的信息量，也就是当前所有的j都可以从之前的i推导出来（这是一个充分的性质）。

依次类推，这样i从0计算到n，期间自然地更新j，就必能得到答案。

但此题特殊之处在于给的是石头的坐标。意味着无法使用连续的0到n的数据结构。 因此，选择使用hashmap来记录（这是必会的技巧）hashMap的key记录石头的坐标，value是记录步数k。 一开始：m(0, 0) = true，接下来，第一次跳，m（1，1）= true，也就是第二个石头坐标s2必为1；

接下来，发现，看第三个石头是没有用的，因为先要看第二个石头后面能跳到哪。我们记录下来： m（1，0），m（2，1），m（3，2）为true； 然后再看第三个石头的坐标s3，究竟有没有机会跳到，也就是看存不存在任何一个m（s3，1），m（s3，2），…

如果一个都不存在，那么说明跳不到；

如果存在，那么要把所有基于s3的下一步跳的结果全部记录下来，对于m（s3，k）就是m（s3 + k，k），m（s3 + k - 1，k - 1），m（s3 + k + 1，k + 1）为true；

注意这里是「正向推」（push）：站在 (s, k) 上，把能跳到的三个格子都标记为可达。它和上面那条逆向式子是同一件事的两种写法——逆向是”问 i 从哪来”，正向是”问 s 能到哪去”。实现上推荐正向，因为本题给的是稀疏的石头坐标，逆向要去反查”i - j 是不是一块石头”，正向只需从已知可达的石头往外推，天然跳过不存在的位置。

依次类推，但要注意，到达同一个m(s, k)可能有多种方式，因此，记录k数组的时候，可以使用set来去重。

Java中就是使用map<Integer，Set>做最终的hashmap，依次扫描石头。

最终的结果是看m（sn）存不存在。

1400. Fermat Point Of Graphs(lintcode)

题意：此题是求无环无向图中，距离其他所有结点总和最小的结点。

解：此题关键是无向无环图，所以图其实是树结构。那么可以使用非dijktra来解题，对于每个root起点使用dfs来计算到其他节点距离，然后只需要O(n)的时间计算一个点距离其他点的距离，同时总距离也计算出来了，这样总的时间复杂度是O(n^2)。

可以进一步优化，找规律，发现，每一条边为总距离贡献的距离，其实是边导致分支的子树结点数量的倍数，也就是分支之后的路径数。这也意味着计算方式变成动态规划：设dp[i]代表以i为根子树的总距离，那么我们知道dp[i] = dp[j] + e(i, j) * cnt[j]， 其中j为i的所有子节点, cnt[j]表示j结点为根的子树结点数量。

最难理解的就是之后的第二步：在保持之前的树结构不变的情况下（也就是与之前dfs起点一样），在进行一遍dfs，这一遍的dfs是计算每一个点到其他任何结点的总距离。对于结点i来说，dp[i]意味着以i为根节点的子树的距离总和，那么接下来要计算的就是i到它的所有祖先结点，以及兄弟结点的距离总和。如何计算呢？

利用数学公式。之前一步的dfs已经计算出了根到所有结点的总距离sum，来看sum - dp[j] - e(i, j) * cnt[j]，意思就是根节点到i以及除了i的j分支以外的结点距离总和； (n - cnt[j]) ) * e(i, j)意思就是边（i，j）对除了j为根子树的其他结点路径的贡献。这两部分加起来的意思，其实就是结点j到除了自己子节点外所有结点的总距离。

理解：也就是把结点j的父节点当作是子结点，第一个部分正好是父节点到除了自己分支以外结点的总距离和，然后在加上自己到父节点这条边对父节点作为子节点的情况下的贡献。注意，计算完之后，下一层新子结点计算时候，他们应该参考的是自己父节点到其他结点的总距离，也就是说sum需要进行更新操作。

1035.Uncrossed Lines

题意：给两个整数数组，数组里面相同数字间可以组队连线，线之间不能交叉，问最多连线可以有几个。

解：此题规律就是，如果同一个位置是相同字母，那么必连，所以，规定dp[i][j]是数组A下标0-i和数组B下标0-j的解，那么，如果i和j所在字母相同，那么问题递归为dp[i - 1][j - 1] ＋ 1；

如果不等，说明i和j不能相连，那么问题规模缩小，说白了，缩减为考虑dp[i-1][j]和dp[i][j-1]中的较大者就好了。

再看基本情况：对于i和j同时为0时候，那么解看当前字母是不是相同，相同则是1，否则是0。在看dp[0][j]，也是看A[0]和B[j]是否相等，如果等则为1，否则递归为dp[0][j - 1]。

在仔细想想，发现，此题和求最长公共字序列是同样的问题：因为线之间不能交叉，和子序列相同是一个意思。

279. Perfect Squares

题意：求出加起来组成正数n，所用的最少的平方和数量，所谓平方和，就是指1，2，4，…。

解：此题是动态规划，要求n，递归到求比n规模小的子问题。对于n来说，它的规模更小的问题是n - i*i，只要保证n - i*i >= 0。 采用自底向上思路就是从1向n计算。

3201. Find The Maximum Length Of Valid SubsequenceI

题意：给出一个整数数组nums，然后要从nums里面取一个最长子序列sub，要求sub里面的每相邻两项的和，mod 2是相等的。

解：动态规划。先分析sub里面的元素情况，实际上每个元素sub[i] mod 2 之后，只有两个值，0或者1；

要满足每个相邻两项加起来相等，那么mod2之后的序列有几种情况，

第一种是00000000…，这样每相邻两项之和mod2的结果都是0； 第二种是01010101…，这样每相邻两项之和mod2的结果都是1； 第三种是10101010…，这样每相邻两项之和mod2的结果都是1； 第四种是11111111…，这样每相邻两项之和mod2的结果都是0；

其他情况，例如00110011…，这就是全由00或者11组成的，其中的00， 01不等了，所以不成立了； 例如1001，其中会出现10和00，也不等，不成立； 例如0110，其中出现了01，11，不成立。

假设dp[i]表示数组{ nums[0], nums[1], … nums[i] } 里面的最长子序列，nums[i]不一定选；

那么，dp[i]可以分为四种情况:

1. dp[i]里面最后选择的两个元素m,n，满足 m % 2 == 0, n % 2 == 0，简称以00结尾

此时对于dp[i + 1]，看nums[i + 1] % 2 是0还是1，

(1)如果是0，那么nums[i + 1]可以配合之前的dp[i]，使得其00结尾的情况增加，

也就是有： dp00[i + 1] = dp00[i] + 1, if nums[i + 1] % 2 == 0

(2)如果是1，那么nums[i + 1]不可以给之前的dp00[i]贡献什么

1. 以01结尾

此时对于dp[i + 1]，看nums[i + 1] % 2 是0还是1，

(1) 如果是0，那么nums[i + 1]可以配合之前的dp[i]，虽然不可对01结尾做贡献，但可以使得10结尾的情况增加！

也就是有： dp10[i + 1] = dp01[i] + 1, if nums[i + 1] % 2 == 0

(2) 如果是1，那么nums[i + 1]不可以对01做贡献，因为011不合法！

1. 以10结尾

同理，

(1) 如果nums[i + 1] % 2 == 0，那么100不合法，不考虑

(2) 如果nums[i + 1] % 2 == 1，那么101，对01结尾的情况有帮助，也就是有：dp01[i + 1] = dp10[i] + 1, if nums[i + 1] % 2 == 0

1. 以11结尾

只有在1结尾的情况下，dp11[i + 1] = dp11[i] + 1；

3202. Find The Maximum Length Of Valid SubsequenceII

题意：给出一个整数数组nums和正整数k，然后要从nums里面取一个最长子序列sub，要求sub里面的每相邻两项的和，余k是相等的。

解：动态规划，思路和3201一致。先分析sub里面的元素情况，实际上每个元素sub[i] mod k 之后，只有k种情况，0, 1, 2, … k-1；

要满足每个相邻两项加起来相等，那么modK之后的序列有几种情况，

第一种，相等型，也就是000000…或者111111…，这样相邻加起来必然相等；

第二种，交替型，也就是abababa…，这样相邻加起来也必然相等，都是（a+b）mod k；

其他情况，例如凑数型，例如1230，行不行呢？不行，因为12和23加起来不等。

假设dp[i]表示数组{ nums[0], nums[1], … nums[i] } 里面的最长子序列，nums[i]不一定选；

那么，dp[i]可以分为几种情况:

假设nums[i + 1] % k == x (0 <= x < k)，那么x可以做的贡献就是:

第一，对于之前xx结尾的，有贡献，也就是dpXX[i + 1] = dpXX[i] + 1；

第二，对于之前的所有xy（其中y != x）结尾的，可以贡献一个xy翻转（成为yx），就是dpYX[i + 1] = dpXY[i] + 1;

其他都不行，例如zy（其中z不等于x），那么zyx不合法；

又例如yx，那么yxx也不合法。

1235. Maximum Profit in Job Scheduling

题意：给出若干工作的开始时间、结束时间和报酬，工作不能时间重叠，求能获得的最大总报酬。

解：这题和 435. Non-overlapping Intervals（见《总结（十五）》）长得几乎一样，但贪心在这里彻底失效，区别只有一个字：权重。

435 里每个区间是等权的（删一个就是删一个），所以「按结束时间排序、能选就选」的贪心成立；本题每个区间带 profit，短而密的一串小活加起来可能远不如一个长活。反例：(0,10,100) 对上 (0,1,1)、(1,2,1)、(2,3,1)，贪心按最早结束会挑一堆 1 得到 3，而正确答案是 100。

等权则贪心，带权则 dp。这是区间调度这一族的分水岭。

推荐解法是按结束时间排序 + dp + 二分，O(NlogN)。

先把所有工作按结束时间升序排序，定义 dp[i] 表示只考虑前 i 个工作时的最大利润（属于上面说的「以 i 结尾」那一类）。对第 i 个工作有两个选择：不做它，结果是 dp[i-1]；做它，则要加上「所有在它开始之前就已经结束的工作」能给出的最优值，也就是 dp[k] + profit，其中 k 是结束时间不超过它开始时间的工作数量。两者取大。

k 用二分来找：由于已按结束时间排序，结束时间数组天然有序，要找的是「最后一个 end <= start」，也就是 start 的 upper_bound 所在下标（见《总结（三）》对 lower_bound / upper_bound 的说明——这里要的正是「比 x 大的那段的左边界」）。

三个要点：

（1）为什么按结束时间排序而不是开始时间。因为转移需要的是「在我开始之前已经全部结束的那些工作」，这是一个关于结束时间的查询；按结束时间排序，结束时间数组才有序，二分才成立。按开始时间排序也能做，但要改成「从第 i 个工作往后」的定义再逆序扫，麻烦一些——这题正好又是上面那个状态方向选择题的实例。

（2）k 不会把当前工作算进去。因为开始时间必然早于结束时间，而结束时间数组升序，所以 upper_bound 的结果必然落在当前工作之前，不需要额外限制搜索范围。

（3）dp[k] 为什么可以直接用。dp 是单调不减的，所以「前 k 个工作的最优」就等于「所有在 start 之前结束的工作能给出的最优」，不用再往前找。

另一种更短的写法是用 map 维护一条单调上升的阶梯（结束时间 -> 到此为止的最大利润）：遍历排序后的工作，用 upper_bound 的前一个位置取出 dp[k]，加上 profit 得到候选值，只在候选值大于当前最大值时才写入 map。那个判断保证了 map 的 value 严格递增，本质是把 dp 数组压缩成只存拐点。面试写第一种（好解释），第二种知道即可。

PS. 本题把三块东西接在了一起：区间排序（57、435）、二分的 upper_bound（《总结（三）》）、带权 dp。属于典型的综合题。反过来看，435 就是本题所有 profit 都等于 1 的特例，那种等权情形贪心即可，见《总结（十五）》435 的家族对照表。

• 上一篇
  Leetcode按题目类型总结（十二）
• 下一篇
  Leetcode按题目类型总结（十四）