LeetCode Dynamic Programming DP

九章DP班归纳:

• 坐标型DP：保存的是坐标的状态；
• 序列型DP：保存的是前x个的状态（数组或cache会多开一个0状态）
• 划分型DP：同序列性；最后一个状态=最后一段；指定段数=> 二维状态，不指定=> 一维
• 博弈型DP：就是A的win会导致B的lose
• 背包型DP：要保存每个重量w作为状态，大多数能滚动数组优化空间。
• 区间型DP：维护两个状态，序列首i，序列尾j。计算顺序必须是按序列长度j-i+1

7.6
120. Triangle: 最简单动态规划，记住要用cache。

7.8
62. Unique Paths: 用cache。
63. Unique Paths II: cache，只不过障碍物的路径=0即可。
70. Climbing Stairs: cache水题
746. Min Cost Climbing Stairs: 必须DP，简单题犯傻

7.9
300. Longest Increasing Subsequence: 对动态规划应该有些许理解

7.10

354. Russian Doll Envelopes: LIS的变种，二维数组排序时，需要将第二个元素倒序排列。其实LIS是一个深坑，详情见下网址：

https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf

在这里对LIS进行短暂说明，如 1,3,2,5,4。

• 首先是DP法，进行一次for循环，获取i位置的LIS（末尾必须为nums[i]），比如nums[i]=4的话，那么4的LIS(4) = max(LIS(1),LIS(2),LIS(3)) +1 = LIS(3) + 1 = LIS(1) + 2 = 3。将LIS函数作为DP函数，维护一个cache即可。那么这样的时间复杂度，最坏为O(n^{2)，最好仍为O(n}2),空间复杂度稳定为O(n)。

• 然后是Patience sorting（耐心排序法），这个算法类似于桶排序。整个算法进行一次遍历，每次只取建桶和入桶两种操作的一种。规则如下：当元素e比每个桶的的末尾值都大时，新建一个桶存放e；如果e比一些桶的末尾值还小，取这些末尾值的最小值，e入最小末尾桶。对应例子，1、3都各自建桶([1],[3])，之后2只能入3的桶([1],[3,2])，5单独建桶([1],[3,2],[5])，4只能入5的桶([1],[3,2],[5,4])。最后结果等于桶的个数。时间复杂度，最坏为O(n^2)，最好O(n)，空间复杂度最坏O(n),最好为O(1)。

• 补充 - 耐心排序优化和证明：

• 优化：显然每次操作检查末尾值的时候，所有末尾值也是升序序列，如例子中的1,3/1,2/1,2,5/1,2,4。那这就可以使用二分查找，而非顺序查找了。时间复杂度最坏降至O(nlogn)。

• 证明：弱对偶性：桶的数量>=LIS，因为桶是按照原数组降序排列的，那么不能使用同一个桶一个以上的数（原本他们就不符合升序，你抽出来就违反规则了）。所以LIS不会超过桶的数量；强对偶性：那可不可以不取某个桶的一个数，获得LIS呢？不行。因为每个桶内部始终是降序的，而每个桶的末尾形成的数组是升序的。那么建桶时，这个数的位置是根据之前桶末尾的最大值确定，可以看成一个指针指向这个最大值。入桶，同样也是指向了之前的一个桶末尾（不一定最大，但可以是一个桶）。那么除了第一个元素，所有数都有一个前置指针，不存在孤立的桶，LIS不能小于桶数。根据弱对偶性，不能大于，只能等于，证毕。

368. Largest Divisible Subset: 没有想象那么复杂，就是单纯的Cache DP。
139. Word Break: Cache DP，middle真的不难。
140. Word Break II: I的基础上加DFS，最骚的是DP居然写错了。

7.11
32. Longest Valid Parentheses: DP状态转换相当难。

• 左括号不保存状态，始终为0。

• i坐标产生'()'时，状态加2，原状态坐标为i-2；

• 产生'))'时，先计算i-1的状态，获得最优解last，比如最优解是4那么可能是'...()())'，则判断i - last - 1是否为’(‘。

• 是，则整个满足状态更新，last + 2 + DP(last - 1),后面这个是关键;

• 否，状态不满足，清0.

7.12
44. Wildcard Matching: 难，看了参考答案，必须用数组DP，不然会MLE。

• 为了把空串包含进去，维护一个m+1,n+1的矩阵。0行和0列，表示s或p是空串。

• 空串能匹配空串，所以DP[0][0] = True，空串不能匹配任何非空串，所以DP[0][j] = False。

• 初始化DP[i][0]，如果DP[i-1][0]成功匹配，且p[i-1]=='*',则DP[i][0] = True。

• 状态转移，匹配p[i-1]和s[j-1]，如果p是字符或者通用字符'?'，则正常匹配s[i-1]，成功则返回DP[i-1][j-1]；如果p是'*',则有三种情况：

• *不匹配任何字符，返回DP[i-1][j]

• *匹配一个字符,返回DP[i-1][j-1]

• *匹配多个字符，返回DP[i][j-1] （跳过s的一个字符）

322. Coin Change: DP Cache。

7.17
403. Frog Jump: 超难题，重点是状态转移是多重的，每个key需要保存的是步数，而不是终点。因为同一个终点，可能由多个路径变化而来，没法获得状态转移方程。

7.18
LintCode 515. Paint House: 没啥难点的基本题。

7.19
91. Decode Ways: 坑点很多的dp题，划分性DP。我的做法：i=0且s[i]=0，则直接返回0了，否则返回1; 通常情况dp[i] = dp[i-1]，如果s[i-1]=1或者（s[i-1]=2且s[i]<7），则dp[i] = dp[i-1]+dp[i-2]。边界情况，i<0，返回1（解释：必定是i=1时会触发下个dp的i<0，且前面的数是非0的，比如17。那么此时对应的情况是两种，所以返回1即可）。
64. Minimum Path Sum: 很简单的DP，不用cache都行。

7.21
553. Bomb Enemy: 要四个方向进行DP，保存这个节点所在的方向有几个敌人。坐标型DP
338. Counting Bits: 类似坐标型DP，难点主要是用java，不熟。

7.22
LintCode 516. Paint House II： 我用了两个cache，其中一个minCache保存上一代最小的两个数字，这样就不用提取所有的上一代了。（果然答案是这个，脑筋急转弯啊？）

7.23
198. House Robber: 真的很简单...
213. House Robber II: 循环版的，我是开的两个初始点，注意：要特殊处理前三个点，因为虽然最后一个点不可以从第一个点开始跳，但它可以从第三个点开始跳。<u>> 简单做法，直接掐头或者去尾，分成两种情况的House Robber。</u>

7.24
337. House Robber III: 树版的，思路不难，但是要记住用cache。
121. Best Time to Buy and Sell Stock: 没看出来用DP，DP法是DP[i]保存第i天卖能获得的最大利润。
122. Best Time to Buy and Sell Stock II: 用的贪心，记住等于的情况直接强行更新了。妈的，直接遇到i+1 > i的，累计差值就行了...

7.26

123. Best Time to Buy and Sell Stock III: 超难DP，阶段转移+序列转移。与之前不同，最多只能两次交易。提出阶段这一概念，具体如下。
所以保存状态f[i][j], i表示该股票在前i天的获利，j表示所在阶段。

• 初始状态：f[0][0] = 0, f[0][j] (j > 0) = 负无穷;

• 转移方程：

• f[i][0] (i > 0) = f[i-1][0]，阶段1只能挂机观望;

• f[i][1] = max(f[i-1][1] + P[i-1] - P[i-2], f[i-1][0])：

• 分析：第一项表示昨天就买入了，今天继续持有，并且获得当天红利（可能为负）；第二项表示昨天还没有买入，今天就买入了，所以暂时没有任何获利，只是状态转移了。

• 例子：3，2，5。f[1][1] = f[0][0] = 0 ，得 f[2][1] = max(f[1][1] + P[1] - P[0] , f[1][0]) = max(-1,0) = 0，所以第二天进入阶段2只能是当天买，而不是在第一天买。

• f[i][2] = max(f[i-1][1] + P[i-1] - P[i-2], f[i-1][2])：

• 分析：第一项表示昨天还在持有，今天就抛出了，并获得当天红利；第二项，昨天已经抛出了，今天仍不买入；

• f[i][3] = max(f[i-1][3] + P[i - 1] - P[i - 2], f[i-1][2], f[i-1][1] + P[i-1] - P[i - 2])

• 分析：这个比f[i][1]多一项，这一项表示从阶段2卖出后马上买入，跳过阶段3的观望。

• f[i][4] = max(f[i-1][3] + P[i - 1] - P[i - 2], f[i-1][4])

• 同f[i][2]

总结：这个题基本表现了Hard DP的一些特点，首先序列DP（第一维）是必须的，表示了要求的东西是什么（这道题是最大收益）；其次第二维是阶段，这种题还没复杂到图的转移，阶段转移是单向的，但是每个阶段的转移需要你至少去分析前面两个阶段，且每种转移方程都是不完全一样的。多做一些这种题，或许可以攻破DP。

7.29
188. Best Time to Buy and Sell Stock IV: 这题不能直接用III的思路套，因为其实3的解法只是清晰，而不是最优的。

• 首先，k可以非常大，那么当大到可以随时交易（k>len(prices)/2)了，就用II的解法，遇到上升就保存。这样能避免一些极端testcase；

• 其次用两个数组，或者长度为2的二维数组就行了；

• 使用新的转移方程：两个数组分别为buy和sell，表示第k次买或卖的利润，但是外循环，每一支股票对全局进行更新。

• buy[j] = min(prices[i] - sell[j-1], buy[j])，表示对于股票i，第j次买，我用sell[j-1]的积蓄买了，是不是比前i-1支股票的第j次买便宜；如果是就更新，不是就跳过；

• sell[j] = min(prices[i] - buy[j], sell[j])，同理，第j次卖，我是以prices[i] - buy[i]的价格套利，还是不管这支股票呢；

• 时间复杂度O(kn)或O(n),空间复杂度O(k)。

8.1
279. Perfect Squares: 其实是比较简单的DP，亮点是python过不了。
LintCode 108. Palindrome Partitioning II: 较难DP，要DP先确定是否是回文串（如果这里不用DP，那么就会让时间复杂度增加到O(n^{3)，然后再DP计算划分次数（总体时间复杂度O(n}2)）。另外一个结论是，尽量别用hashset，开销比array大不少。

8.3
LintCode 437. Copy Books: 较难dp，状态转移包括minmax，具体转移方程是f[i][j] (i表示前i个人，j表示前j本书）：
f[i][j] = min(max(f[i-1][p],A[p]+ ... + A[j-1]), max...) for p in [0,j)
LintCode 394. Coins in a Line：简单博弈性DP，你的负等于上家的只能胜。
LintCode 92. Backpack: 背包问题，属于特殊性DP。双状态，一个维护查看了多少个物品i不必多说，另外一个状态维护的是0~m总重量，保存的是能否拼出这个重量j。这是背包问题的特殊性，虽然最后返回的是能装的最多的重量，但是保存的却是能否拼出某个重量。（这应该是累和问题的特殊性，如果状态是某列表的最大值，如copybooks，那么这种解法直接失效了）

8.4
LinCode 563. Backpack V: 背包问题5，也是滚动数组就足够维护状态了。new[j] = old[j] + old[j - nums[i-1]] 。
LinCode 562. Backpack IV: 滚动数组维护状态，在5的基础上，加入一个while循环，不停地减nums[i-1]，比如，f[7] = old[7] + old[7-3] + old[7 - 3 -3] ...。
LintCode 125. Backpack II: 额外的背包问题联系，掌握套路过后，只是转换方程有变化而已。
LintCode 440. Backpack III: python装怪啊。
LintCode 799. Backpack VIII： 带数量的金币分配，问题不大，类似于IV，只不过是或连接。

8.5
516. Longest Palindromic Subsequence: 区间型DP，注意计算顺序有套路，要按照序列长度计算。另外python过不了，java能过。