DP 算法题目的思考

dp全称是动态规划，是一类被人又喜欢又讨厌的题目。喜欢是因为找到递推关系之后题目就变得简单了，讨厌的原因是这类题目常常很难想到递推关系。

dp的核心思想就是把一个复杂的问题分解成简单的子问题，并且可以利用递推的方式来解决。所有dp题目的核心是：

  1. 递推公式 deduction formula
  2. 初始化 initialization
  3. 空间优化 space improvement

路径数量

这类题目就是看有几种方式可以到这个点，然后把这几种方式的路径加起来就可以。这是自下而上的思想，对于青蛙跳的那道题也可以自上而下利用递归的思路解题。只要可以跳到，就可以变成一个子问题，把这个点当做起点来进行。

word break 这类题目就可以使用相同的思想。思路是判断前i个是否可以组成，之后就判断这从i到j是否是一个单词。如果要记录下来所有的组成可能的话就可以使用dfs了。

当dp会超时时，如果只是问是否可以到，可以利用dfs来greedy的查找。

最长问题

耐心排序。Dp和二分查找也可以结合，例如找最长递增子序列的题目。在array那里已经提到了这道题，dp的思想在这里是这样的，我们先建立一个数组ends，把首元素放进去，然后比较之后的元素，如果遍历到的新元素比ends数组中的首元素小的话，替换首元素为此新元素，如果遍历到的新元素比ends数组中的末尾元素还大的话，将此新元素添加到ends数组末尾(注意不覆盖原末尾元素)。如果遍历到的新元素比ends数组首元素大，比尾元素小时，此时用二分查找法找到第一个不小于此新元素的位置，覆盖掉位置的原来的数字，以此类推直至遍历完整个nums数组，此时ends数组的长度就是我们要求的LIS的长度，特别注意的是ends数组的值可能不是一个真实的LIS，比如若输入数组nums为{4, 2， 4， 5， 3， 7}，那么算完后的ends数组为{2， 3， 5， 7}，可以发现它不是一个原数组的LIS，只是长度相等而已。

可以把相同的思路放在二维数组上解决Russian envelopes的问题。信封的宽度还是从小到大排，但是宽度相等时，我们让高度大的在前面。那么现在问题就简化了成了找高度数字中的LIS，完全就和之前那道Longest Increasing Subsequence一样了。把高度放前面为了防止相同宽度的互套。

还有一些类似找相同行列的特性的题目，例如找最大十字架和enemy and bomb,可以使用两个方向同时扫的方法(从右和从上、从左和从下)，记录出现的次数，这样可以方便计算。

股票问题

这类问题存在多种的转态转移方程，有的时候不太容易搞清楚。方法就是从基础的情况开始想，然后思考之间的关系。 可以从数组开始，之后再化简成为单个变量

For each of them we make an array, buy[n], sell[n] and rest[n].

buy[i] means before day i what is the maxProfit for any sequence end with buy.

sell[i] means before day i what is the maxProfit for any sequence end with sell.

rest[i] means before day i what is the maxProfit for any sequence end with rest.

Then we want to deduce the transition functions for buy sell and rest. By definition we have:

  • buy[i] = max(rest[i-1]-price, buy[i-1])
  • sell[i] = max(buy[i-1]+price, sell[i-1])
  • rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

Where price is the price of day i. All of these are very straightforward. They simply represents :

(1) We have to rest before we buy and (2) we have to buy before we sell

One tricky point is how do you make sure you sell before you buy, since from the equations it seems that [buy, rest, buy] is entirely possible.

Well, the answer lies within the fact that buy[i] <= rest[i] which means rest[i] = max(sell[i-1], rest[i-1]). That made sure [buy, rest, buy] is never occurred.

A further observation is that and rest[i] <= sell[i] is also true therefore

rest[i] = sell[i-1] Substitute this in to buy[i] we now have 2 functions instead of 3:

buy[i] = max(sell[i-2]-price, buy[i-1]) sell[i] = max(buy[i-1]+price, sell[i-1])

游戏问题

一般都是有两人玩游戏，重点是就是搞清楚选择了和没选择的状态的不同以及转换。

数组/string比较

这类题目的代表就是regex，可以分情况讨论分情况决定下一个是否是符合的。基本思想都是使用一个二维数组，i和j分别代表第一个数组第i个以及第二个数组第j个。如果数组dp[i][j]=1，说明这是符合要求的。

另外一个相关的问题是最长公共序列的经典dp问题,这个题目的思想和regex几乎相同，把问题分成两类，第一类是a[i]!=b[j],第二类是a[i]=b[j]。如果两边相等的话，就可以使用之前dp[i-1][j-1]+1的结果，如果不等的话则是max(dp[i-1][j],dp[i][j-1])。题目可以用递归+memorization解决。

相似的题目还有edit distance经典题型，思路是相同的。利用二维数组表示，如果相同，和之前dp[i-1][j-1]相同，如果不同则是1+min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])。这里是就增加，删除，替换三种可能。

背包问题

这是dp另一类经典题目，在一个条件被限制的情况下如何获得最大。原始的背包问题是这样的，背包有限制大小，每个物品有大小和价值，在大小限制的情况下如何做到最多的价值。解法包括自顶向下和自下而上。本质上都是穷举可能的的大小，之后得到最大的价值。这个方法把指数次的时间复杂度降到O(nS)。dp[n][S]表示记录第n个物品时在S的情况下的最大价值。

prefix sum

把数组前n个加起来，可以用来weight probabilty。可以用binary search获得结果。

全局最优,local 最优

经典dp，m个城市k个邮局怎么可以达到全局最短。基本思路就是从放一个邮局的角度开始思考。如果从第i个城市到第j个城市之间增加一个邮局该怎么放。这时候就需要知道从第i到第j的最短整体距离是多少。得到这个递推公式。

sum[i][j]:在第i个村庄到第j个村庄中建立1个邮局的最小耗费, 村庄的坐标已知分别为p1,p2,p3,p4,p5,p6;那么，如果要求sum[1][4]的话邮局需要建立在2或者3处,放在2处的消耗为p4-p2+p3-p2+p2-p1=p4-p2+p3-p1 放在3处的结果为p4-p3+p3-p2+p3-p1=p4+p3-p2-p1，可见，将邮局建在2处或3处是一样的. 所以可以使用这个公式。

sum[i][j] = sum[i][j-1] + p[j] -p[(i+j)/2]

dp[i][j]:在前i个村庄中建立j个邮局的最小耗费

j<k<=i

dp[i][j] =min(dp[i][j],dp[k][j-1]+sum[k+1][i])  

股票可以进行K次交易的问题，我们也可以使用相似的思路， 一个是到目前为止最好的结果信息（全局最优）， 另一个必须包含新加进来的元素的最好的结果信息（局部最优）。global[i][j]是一个是当前到达第i天可以最多进行j次交易，最好的利润是多少，local[i][j]是当前到达第i天，最多可进行j次交易，并且最后一次交易在当天卖出的最好的利润是多少。global[i][j]=max(local[i][j],global[i-1][j])，而局部是local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)，diff是今日的变化。根据定义可以知道，直接+diff是不会改变交易次数的。