动态规划杂谈
放弃思考选哪个offer的问题了，我们来扯扯动态规划。
本篇适合：做了很多动态规划题了，但是看到微软这次校招笔试的第二题 http://hihocoder.com/problemset/problem/1400
还是很懵逼的同学
其实直到今年5月，我都还是对动态规划比较懵逼和恐惧的。
刷过很多背包，刷过LIS、LCS……然而题目稍微复杂一点，秒炸。
果然鹅厂的实习生笔试题来了个 最长回文子序列 ：
然后果然不会做。
之后问学弟，直接甩我一个回答：
这不是区间dp裸题吗？
dp[i][j]表示从i到j最长回文子序列的长度。如果str[i]==str[j] , dp[i][j]=dp[i+1][j-1]+2否则，dp[i][j]= max (dp[i+1][j] , dp[i][j-1])
这个题之后，突然开始开窍了……
==========================================
就我目前这个渣水平看来，动态规划的设计，其实不外乎3步：
1、确定基本状态方式
2、加状态以能在转移的时候不受牵制
3、打磨转移的细节。
第一步是个单选题，就是目前没见人系统整理过，有选项这一说。
你的转移过程，从小问题到大问题，你的最小问题要长什么样？
01背包？或者上面提到的微软的题？从前到后（从第1件，到最后一件）
（其实绝大多数动态规划起手先试试看从前到后作为基础状态，并没有大错）
最优矩阵乘法？从小区间，到大区间（也就是上面提到的区间dp）
在树上的问题，比如，树的最远2点，比如，works application的无线路由器？
以i为根的子树作为状态（树形dp）
要枚举子集？比如，小规模的旅行商问题？
以所有可能的子集作为状态（因为一般用二进制的01表示这个元素在不在子集中，进而把子集这个数学概念/对象，变成一些int范围内的数值，所以称作，状态压缩动态规划）
等等等等。
（当然还有基础状态更加复杂的动态规划，但这些短期看不会在面试题中出现了，（而且我也不会了），按下不表）
==========================================
至于第二步
曾经有一次个人赛，题目我已经找不到了……
当时那是最后一个题，动态规划设计感觉黔驴技穷——设计了一种状态，但是根本没法转移，我还要考虑另一个参数——的时候，开始瞎翻手边的书。
突然看到一句话，豁然开朗：
当发现状态无法转移后，常见的方法是增加维度，即增加新的因素，更细致地描述状态。
（刘汝佳《算法竞赛入门经典（第二版）》）
或者用一些糙的话来讲这个道理：
- 诶呀，我做出这个选择，要看前面做过的选择的脸色？
- 你要考虑前面什么东西，就把那个东西加为状态
- 诶呀，这里有个数量/blabla的限制条件？
- 限制条件？转移过程中控制不能的，
加状态。
比如上面微软的那个题：
我从前往后考虑
当前这个字符要不要？要的话还得看前面一个字符？？？这直接按长度设置状态，不行啊！
那直接加一维度，表示结束字符啊！这样你后面转移不就只要字符没事就选上，冲突就不作为转移来源了嘛~
works application这个题同理：
限制路由器个数？
加一维度状态，表示用了多少路由器。
我的转移要看孩子节点的情况（才能算对价值）？
加一维度，表示根节点状态，这样父亲节点按需拉走。
=======================================================
一句话，dp没有那么可怕
找基底，把牵制变状态，然后？面对面试差不多了，优化再按需考虑吧！
脑子有点乱，当我的胡诌吧，以上。
