DP 算法题目的思考

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

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

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

路径数量

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

股票问题

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:

• 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.

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:

全局最优,local 最优

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])