理论

什么时候用?

• 求最大/小/优值
• 判断是否可行
• 统计方案个数

什么时候不用?

• 求具体方案， 而非统计方案个数
• input为set, 而非array（DP要求不能换位置）
• 暴力解已经是多项式时间 （DP擅长将O(2^n)的解法优化为O（n^2))

可以用dp的特征

• 最优子结构
• 重叠子问题

八大类型

• 坐标型（15%）
• 接龙型（30%）
• 划分型/匹配型/背包型
• 区间型/树图型/博弈型(90%博弈型都为DP）

按状态分-两大类型

• 坐标型（dp[i] 表示以i结尾的最大/优/trueOrFalse 值）
• 序列型（dp[i] 表示前i个的最大/优/trueOrFalse 值）
  • f[i]表示以i个位置为结尾的答案，前i个的最大/小/。。， 不一定包括包含第i个；
  • 用dummy dp[0]简化程序

DP vs 递归

动归四要素	递归三要素
1. state	1. 定义
2. function	2. 拆解（方程)
3. initialization	3. 出口（初始化）
4. answer

什么时候用记忆化搜索？

• 1. 状态转移特别麻烦，不是顺序性
• 2. 初始化状态不是很容易找到(e.g. stone game)
• 3. 由大到小

Tips

• 滚动数组优化 e.g f[i] = max(f[i-1], f[i-2]+1) + 1 => f[i%3]=max(f[(i-1)%3], f[(i-2)%3]+1) + 1

Problems

1. 坐标型

• f[i]表示从起点至i的方案个数，一定包含第i个，不能有循环依赖， 最大/小/。。, dp[0]代表第0个元素是最大/小/。。。

62. Unique Paths用一维数组即可
63. Unique Paths II 64. Minimum Path Sum可优化至1d，或覆盖原矩阵
120. Triangle 576. Out of Boundary Pathsfor k in range(maxMove):将oldGrid中边界的move数加入res中，newGrid[x][y]中存有多少步move可以移到(x,y)，同时将移动到的点的位置放入newStartSet中，用newGrid, newStart替换old, \

1289. Minimum Falling Path Sum II滚动dp， 每行记录min, 2ndMin, minCol, 2ndMinCol, O(n^2), O(1)
403. Frog Jumpdp={stone:set(之前一步jump size)}，对stones按顺序遍历，若diff + step + stone in dp， 则更新dp[diff + step + stone].add(diff+step)，其中diff=[-1,0,1], O（n^2)\

dungeon-gameMove backward from lower right corner

out-of-boundary-paths不要double counting minimum-falling-path-sum

2. 接龙型

• 一般为序列型
• 若dp[i]无法用dp[j](j < i) 表示， dp[i]表示以i结尾的值； 否则，dp[i]表示前i个的最大/优/trueOrFalse 值。

368. Largest Divisible Subsetdp[i]=(以num[i]为终点的subset的长度，可以被num[i]整除的最长subset指数)， 得到dp后，由dp[maxIdx][1]逆序推得序列\

139. Word Break判断s[i-length+1:i]==word && dp[i-length]
198. House Robberdp[i] = max(dp[i-1], dp[i-2] + nums[i])
213. House Robber II可以视为houseRubber(nums[1:n])和houseRubber(nums[:n-1])
322. Coin Change设dp[0.....amount], for c in coin: dp[i]=min(dp[i-c]+1, dp[i])
377. Combination Sum IV类似于coin change, 遍历num, dp[amount]+= dp[amount-num]
221. Maximal Squaredp[i][j]=min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])\

123. Best Time to Buy and Sell Stock III用b1, s1, b2, s2四个变量，每遍历一个数,逆序更新四个变量，都取max
188. Best Time to Buy and Sell Stock IV若k/2>n，则可无限次交易，低买高卖 2）若k/2<n，for k: 设buy[i], sell[i]代表交易i次股票后的净值，对price:prices依次更新buy, sell
714. Best Time to Buy and Sell Stock with Transaction Fee用sold[i] = max(sold[i - 1], hold[i - 1] + prices[i] - fee)， hold[i] = max(hold[i - 1], sold[i - 1] - prices[i])\

746. Min Cost Climbing Stairsdp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
1137. N-th Tribonacci Number同上\

790. Domino and Tromino Tiling用f[i], p[i]分别记录覆盖完整i块,和一般i块可能的方法数
1326. Minimum Number of Taps to Open to Water a Gardendp[i]表示从[0, i]需要开多少个水龙头，遍历每个水龙头，对于范围之内，dp[j]=min(dp[j], dp[i-range]+1)\

1235. Maximum Profit in Job Scheduling对(end, start, profit)排序，dp[i】表示排序第i个任务endtime时的maxprofit(包括之前),对每个任务的start，用二分法找到dp中插入位置，若dp[i][1]+p>dp[-1][1]，则append至dp，O(nlgn);法二：heap中存（endtime, profit)， O(nlgn)\

【难】2713. Maximum Strictly Increasing Cells in a Matrix为了避免重复，可以用row[i],col[j]记录目前为止出现的最长序列；将nums华为dp[val]=[(i,j),...],依照val由大到小遍历，更新res[(i,j)]，以及row[i],col[j]\

629. K Inverse Pairs Array找规律，由n=1开始，如1,2,3有0组逆序,将4插入3之前可产生一组，插入2之前可产生2组，故有dp[n][k]=dp[n-1][k]+dp[n-1][k-1]+...+dp[n-1][k-n+1],进一步地可由cumsum优化，用o(nk）时间，prev和curr两个数组可将空间优化为O（k).\

823. Binary Trees With Factorscnt[val]表示以val为父节点，可以建立多少树，for i：for j in range(i）：若v1*v2 or v1*v1 in cnt[v1 * v2] += (2) * cnt[v1] * cnt[v2]\

1531. String Compression IIdp(i, last_char, last_char_cnt, deletedCnt)，因为有四个维度，用cache更方便；其中当last_char_cnt in (1, 9, 99, 999)时，若s[i]==last_char, res_length+=1\

935. Knight Dialerhard code出每个数字可以跳到哪个数字，再dp， O(nk)~O(n)\

446. Arithmetic Slices II - Subsequencedp[i][diff]表示以num[i]结尾的diff的序列有几个（包括长度为2），若之前已经出现过dp[j][diff],说明字串长度已经大于3,res += cnt + 1, O(n^2)
1155. Number of Dice Rolls With Target Sumdp[i]表示构建i有多少种方法，for _ in range(k):构建dp2, dp=dp2\

1359. Count All Valid Pickup and Delivery Optionsdp[i][j]取决于dp[i-1][j]和dp[i][j-1]\

727. Minimum Window Subsequencedp[j][e] = s表示s1[:e]以s1[e]结尾的substring 最大左边指数s, s.t. s1[s:e]包含s2[:j]\

1639. Number of Ways to Form a Target String Given a Dictionarydp[i][j] = number of ways to make target[:i + 1] using first j + 1 characters\

number-of-longest-increasing-subsequence

在LCI的基础上加一个count vector记录以每个字母结尾的最长子串的个数。

student-attendance-record-ii

continuous-subarray-sum subarray-sum-equals-k

Best Time to Buy and Sell Stocks unique-substrings-in-wraparound-stringUse a seperate count table recording the count of all possible substring ending in c, 以避免重复。 essentianlly, it is caching all the substring ending in c, since the length of the substring determine the substring uniquely, storing count is enough.

maximum-length-of-repeated-subarray largest-divisible-subset

minimum-cost-for-tickets

dp[i]表示min cost to cover trips in days up to day i.

• 仅仅dp[i] 无法表示A[:i] 的状态， 用两个array分别表示extra status, 进一步的， 可只用两个current value 来代替数组. wiggle-subsequence longest-turbulent-subarray

典型的拆成两个dp array, 再用两个当前状态优化dp array. minimum-swaps-to-make-sequences-increasing 差拆前一对是否互换两张情况。

new-21-game

绿皮书解法， solved backward

distinct-subsequences-ii

Notice that the if not duplicates, the number of subsequenct up to index i, is simply the sum of all subsquence ends at j(j < i), equivalent to 2^i. When there is duplicates, it will be sum from k to i-1, where k = last appearance of s[i], so the result is 2 ^ dp[i-1] - dp[k - 1].

paint-house

用r,g,b分别记录min cost last paint with color rgb up to house i.

number-of-corner-rectangles

依次遍历每一行，记录colum pair出现的次数。

3. 划分型

• dp[i][j] 代表在分别在s1, s2的划分点 5. Longest Palindromic Substringdp[i][j]表示s[i:j]是否为回文，循环初始化对角线次对角线后，for 子字符串长度 法二：对每个字符中心展开，O（n^2))
  343. Integer Breakdp[i]代表i能分解得到的最大乘积; dp[i] = max(dp[i], max(i - j, dp[i - j]) * max(j, dp[j]))
  689. Maximum Sum of 3 Non-Overlapping Subarrays提前计算好以sum(num[i-k,...,i]), 令w1, w2, w3 = intStart[i], intStart[i + k], intStart[i + k * 2]，遍历i， 更新total1, total2, total3（分别表示前1，2，3块区域的最大和）,O(n)\

1478. Allocate Mailboxesdp[i][k]表示在houses[:i]建k个邮箱的最小距离；dp[i][k]=min(dp[j][k-1]+dist(house[j-1],...house[i]中建一个邮箱）)，dist[j][i]需要提前算好,O(kn^2+n^3))
1043. Partition Array for Maximum Sumdp[i]代表以arr[：i]的结果，则dp[i]=max(dp[i], dp[j]+max(arr[j:i])*(i-j)，遍历j=i-1,...,i-k时， 更新res
【不懂】2945. Find Maximum Non-decreasing Array Lengthdp[i]表示nums[:i]所组成的最长长度，v[i]表示对应dp[i]下最后个数字,O(n^2)=>TLE, 为了找到对于i， sum[j+1:i]>v[j]，可以将sum[j:i]化为presum[i]-presum[j]>v[j]=》presum[j]+v[j]<presum[i],为了保证presum+v[j]递增，将其放入单调栈，从而可以使用二分法\

【不懂】1335. Minimum Difficulty of a Job Schedule类似于2945， dp[d][i]表示第d天，前i个任务的min difficulty， dp[d][i]=min(dp[d-1][j]+max(A[j:i]))，j=0,...i, O(n^2d);用单调栈存递减,dp[d][i]=min(dp[d][j]+A[i]-A[j], dp[d][stk[-1]]),其中j为stk.pop()直至stk[-1]>A[i]，即比A[i]小的A[j]，另外，dp[d][i]=min(dp[d][i],dp[d-1][i-1]+A[i])，O(nd)\

Scramble String用三维DP即可表示两个字符串中的分别两个子串， 因为其长度相等， 最后个坐标可被推导， 所有n^4->n^3

palindrome-partitioning-ii用二维超时， 更好的方法是利用parlindome的性质， 在每个字符左右展开， 另外，用dp[i] 记录A[:i]最小切割次数

problems/largest-sum-of-averagesdp[i][k]代表A[:i]分成k组最大平均

689. Maximum Sum of 3 Non-Overlapping Subarrays The official solution sounds like brute force, but actually in O(n). The idea is very innovative, since the size of the subarray must be k, we can create left[] keep tracking of the best sum of k-size subarray up to index i. and similarly for right[], have these two arrays, we just need to search the middle k-size array within [k, windowSize - k], if the sum of it plus left[] and right[] smaller than the optimal so far, update it.

4. 区间型

• 将数组区间用二位DP表示
• 【不懂】和划分型的区别 guess-number-higher-or-lower-ii

312. Burst BalloonsSince the last ballon to be burst in the subarray is sure to adjacent to the the left and right end of the subarray, so it is better to think reversely : helper(left, i-1) + helper(i+1, right) + nums[left-1]*nums[i]*nums[right+1]，其中i为最后爆的气球，其左边的[left, i-1]全都爆了，包括left和i-1；用top-down+cache更容易 546. Remove Boxes

这道题和leetcode 312. Burst Balloons一样都属于 not- elf-contained subproblems, where the maximum coins of subarray nums[i, j] depend on the two numbers adjacent to nums[i] on the left and to nums[j] on the right. Problems without self-contained subproblems usually don't have well-defined recurrence relations, which renders it impossible to be solved recursively. The cure to this issue can sound simple and straightforward: modify the definition of the problem to absorb the external information so that the new one is self-contained. 这里定义 T(i, j, k) = the maximum points possible by removing the boxes of subarray boxes[i, j] with k boxes attached to its left of the same color as boxes[i]

strange-printerdp[i,j] = max(dp[i,k+1] + dp[k, j]) for all s[k] == s[i]

remove-boxes This is hard, I cannot even fully understand the solution.

5. 匹配型

• 往往都是两个字符窜 10. Regular Expression Matching若 p[i-1]:(1)dp[i][j]=dp[i-2][j](零重复）（2）若*之前的字母与s[j]相符或s[j]=='.'，则dp[i][j]=dp[i][j-1](比较p[:i+1]与s[:j])\

44. Wildcard Matching设dp[np+1][ns+1]，若p[i-1]=='*‘， dp[i][j]=dp[i-1][j]|dp[i][j-1],初始化dp[0][j],dp[i][0]；'*'要特殊处理\

72. Edit Distance

if word1[i - 1] == word2[j - 1]:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]+1, dp[i-1][j] + 1)
else:
dp[i][j] = min(dp[i-1][j-1] + 1, dp[i-1][j]+1, dp[i][j-1] + 1)

97. Interleaving Stringdp[i][j]表示s1[:i]s2[:j]是否可以组成s3[i+j],若s1[i]==s3[i+j]且dp[i-1][j],则为True， 对s2[j]亦然\

1143. Longest Common Subsequencedp[i][j] represent the longest length obtained by A[:i] and B[:j]
1312. Minimum Insertion Steps to Make a String Palindrome问题转化为找到s中最长子序列(如长度为l)，则需插入n - l个字符；找到s中最长子序列为典型的longest common subsequence 问题(s2 = reverse(s))\

【不懂】1187. Make Array Strictly Increasing对于每个arr[i]， 若>prev, 则更新prev；同时在arr2中找到最小>prev的值，替换arr[i], dp[prev]=cnt\

[难】691. Stickers to Spell Word用state （范围为(0,... 1<<len(target)]）存dp状态，从dp[0]开始向上,for 每个stick，若能加上称为新的state，更新dp[new state]， O(2^T*S*T)，S为stick个数，T为target长度；优化：将被大stick包含的小stick移除\

2060. Check if an Original String Exists Given Two Encoded Stringsdfs+memo,记录dfs(i,j,memo)，返回dfs(-1, -1, 0)；不知道为什么答案都是top down\

2565. Subsequence With the Minimum Score找到没有交集的两个最长前缀和最长后缀，不用考虑当中元素\

Longest Common Subsequence 的变种(1d -> 2d, dp[i][j] represent the longest length obtained by A[:i] and B[:j] distinct-subsequences

dp[i][j] 表示length of match for s[:i], t[:j]. notice that for subsequence, it is more common to use dp[i][j] to record max value from all previous data, instead of val of s[i], t[j], if so, that means we have to go from k = i,i - 1, ... 0 to find update value, makes it O(n3).

6. 背包型

• find maximal value for the first i items, constrained by weight <= j. dp[i][j] = max(dp[i][j], dp[i-1][j-weight_i] + value_i)
• find minimal weight for the first i items, constrained by value >= j. dp[i][j] = min(dp[i][j], dp[i-1][j-value_i] + weight_i)

322. Coin Changedp[amount]表示最小可以以几个硬币得到amount
518. Coin Change IIdp[coin][amount]表示用coin[i:]来表示amount可以有几种方法；进一步的可以化简为1d, for coin(每次增加一种coin): for i in amount: dp[amount] += dp[amount-coin],即每增加一种coin带来的额外方法数
377. Combination Sum IV调整coin change中for loop的顺序（i.e. for amount: for coin: ...)得到的答案完全不同，代表的是考虑顺序的组合个数，e.g. [1,1,2]和[2,1,1]为两种不同的方案
416. Partition Equal Subset Sum 2189. Number of Ways to Build House of Cards本质上是coin change问题（有一些硬币2,5,8,11,..., 欲构成n,每种硬币只能使用一次，有多少种可能性），这里因为只能使用一次，所以遍历amount需要逆序。
【不懂】956. Tallest Billboard背包型,记录dp[diff]=taller,遍历rod, 更新dp
2742. Painting the Walls背包型，每次选择是否刷ith墙；dp[i][remain]表示当考虑第i墙时，还有remain个墙没有刷到，dp[i][remain] = min(dp[i + 1][remain]#不刷,dp[i + 1][max(remain - time[i] - 1, 0)] + cost[i]#刷)
1125. Smallest Sufficient Team用bit mask表示人的技能，以及当前所有技能,dp[skill bit]=[用到的人], 遍历每个人，遍历dp中已经习得的技能组合, comb = curr_skill|people_skill，更新comb
983. Minimum Cost For Tickets设置cost[365]， 同时设置指针i指向days\

partition-equal-subset-sumdp[i][j]表示我们是否可以在前i个数找到序列和为j partition-equal-subset-sumdp[i][j]表示能否用前i个数来的到和j

7. 博弈型

486. Predict the Winnerdp[i][j]表示剩余nums[i...j]时，最大的score diff\

guess-number-higher-or-lower-ii

can-i-winuse DFS + cache to memorize the win-loss prob of each state stone-gamestraightforward

8. 其它