动态规划
动态规划一直以来，算是一个弱点，前几腾讯的实习生笔试有道区间DP的题目，当时只能暴力的使用了递归，存在大量的重复计算，时间复杂度会达到O(N^2)。所以今日，查资料，从基础学习DP。
首先参考的资料是知乎回答：什么是动态规划？动态规划的意义是什么？ 。王勐和徐凯强帮我建立的对DP的概念认识和理论认知，在这点上，两位的答案要比书中讲解的好，因为更直白。
之后，扔掉他们两个的回答，对最长递增子数列（LIS），自己分析，写状态定义，写转义方程，写代码实现。当然在实现中还是踩了很多坑，比如数组的初始化值。
后续完成了LeetCode OJ上以前遇到过的DP题目，帖到GIST动态规划合集。后面做的动态规划题目，也会继续贴到这个GIST上。
看了知乎的回答，并不能让人掌握DP，只能在你了解DP的时候，帮助你梳理自己对DP的理解。
因此，总觉的内心空空的，把握不住DP，下载了刘汝佳的《算法竞赛入门经典》（简称算法入门）又找到一本《算法设计和分析基础（第三版）》（简称算法设计基础），算法设计基础的动态规划比第二版的要好，作者说更简单，有种由浅入深的感觉。当看到第一个例子是斐波那契数列的时候，我就感觉，例子是不是太简单了，转而去看算法入门。
虽然算法入门已经被黑出翔了，当对我而言，这本书还是有很大帮助的，数字三角形的问题很基础也简单易懂，也讲解了递归，记忆化搜索，等一些技巧，对，按前面知乎提到的，这只是技巧。在看DAG和最长路、最短路的时候，了解了边界情况，初试值的设定，提高阅读性的技巧。然而这已经耗尽了一上午、一下午加部分晚上的时间。晚上跳过了两个小节，去看了一下9.4经典模型，这个时候，已经能尝试着去自己定义状态和转义方程。
再次回到《算法设计和分析基础》，8.1节比斐波那契数列深入了一些，我研究了每个例子的状态和他们的转移方程，列出边界，并且动手去模拟算法，之后去做8.1节的习题，这些题目是例子的变形，很庆幸，自己能写出结果来，确实是由浅入深。
随着我对DP的基类，我对简单的DP有些许自信了，并且应该做出下面的总结，即便，在将来看来是错误的：
- DP是一种思想，将问题分解为子问题，子问题之间存在依赖性。
- DP的核心是定义状态和转移方程。仔细思考如何定义状态：比如是从i开始的结果（数字三角形），还是以i结束的结果（Coin-row，Change-making，Coin-collecting）。
- 清楚当前问题的边界。
- 写出尽量完备的测试例子。
- DP的题目大多是最优解的考察，如果是最大、最长等问题我一般会先写出
F[i] = max{___}，然后向里面去填空。 - 去实现DP的时候，函数不应该太大。不然，很可能你已经写错代码了，就像机器学习中的过度拟合一样。
- DP有两个提到的是自上而下（top-down）的DP，上推（bottom-up）的DP，当然还有其他版本的DP。
- DP的效率并不一定比分治、贪心快，比如LIS。
- 如果终点时固定的，状态的定义往往是从起点，到当前位置，所得到的结果。
以下更新于2016年4月5日。
既然DP的核心是状态的定义和转移方程，定义状态的基础是确定自变量和因变量，因变量就是题目要求的最优解，而自变量就需要根据题意设定了，在确定题目之后，一般就能发现与因变量相关的一些变量，并不能拿这些变量全部作为自变量，应当探索着取其中的一个作为自变量，如果不行，再取两个。
这面罗列一些，白天总结的自变量和因变量。
Coin-row
一行硬币，取若干硬币，使得硬币的和最大，取出的硬币不相邻。
- 因变量：取出的硬币的和。
- 自变量：通常来讲是硬币的数量和币值，但这里是已经固定的硬币的排列，并且是最优化问题，最大的和，这里把自变量n定义为前n个硬币。
- 再完善因变量：满足取出条件的最大和。
- F（k）：前n个硬币，满足不相邻条件，所能得到的最大和。
- 结果：max{F（k）| 1 <= k <= n}
Change-making
d[m]为币值，给你一个金额amount，使用最少（多）数量的硬币组成amount。
- 因变量：硬币的数量。
- 自变量：因变量同时受币值和amount的影响，这里定义amount为自变量，因为不同的amount之间，可以通过d[i]转移。把amount和d[i]换为另外一个amount问题，比如，amount为10块钱，d[i]为5块的币值，那么就可以把F（10）和F（5）关联起来，由于还存在其他币值，可以把F（10）与所有的F（10-d[i]）关联起来，选取期中的最优解。这是终点固定的问题：从节点0出发，到终点amount的最短路径。
- F（k）：当前amount所需要的最少的硬币数量。
- 结果：F（n）
数字三角形问题
数字三角形问题。有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来。求最大和。
- 因变量：路径上的最大和。
- 自变量：这是一个二维的，所以自变量为
(i,j)，起点固定。 - F(i, j)：自(i,j)开始，能得到的最大和，包括(i,j)本身。
- 结果：F(1,1)
LIS
- 因变量：
- 自变量：
背包问题
一个容量为W的包，一堆重量分别为w1…wn，价值分别为vi…vn的钻石，问如何用包装下尽量多的钻石，让总价值最大。
- 因变量：被选出来的钻石的总价值。
- 自变量：因变量受W的限制，以及每颗钻石的重量。借鉴change-making的思路，把W设为自变量，将F(W)定义为能钻石的总价值，转移方程可以描述为：
F(k) = max{ F(k-wj) + vj | j是剩余的钻石 }，这样剩余钻石的集合一直在变，关键是它们不一定连在一起，不容易处理。 - 自变量再尝试：转换为DAG问题，我们固定一个起点，定义F(k)为前k个钻石，在W的限制下能获得的最大总价值，其实这是有缺陷的，比如我要第k+1个，而不要第k个能得到最优的解，此时w(k+1)比w(k)大，但恰好又能装进去，但按照F(k)的定义，我们得不到最优解。这个时候，我们已经离找到正确的定义比较近了。
- 自变量再尝试：既然因变量还受W的限制，我们把容量也作为一个自变量，设置二元自变量，F（i，j）定义为：前i个元素，在容量限制为j的情况下，所能获得的最大价值。这时候对于i而言，有两种状态，一种是包含了i，一种是没有包含i，若包含了i，
F(i,j) = v(i) + F(i-1, j-w(i))，如果没有包含i，则F(i,j) = F(i-1, j)。而F(i,j)是两者之中的最大值，这里面是有边界的，就是如何判断是否包含i，在表达式F(i,j) = v(i) + F(i-1, j-w(i))中，存在j-w(i)，这个就是边界，如果j>=w(i)，那么可能包含i，反之，一定不包含。 - 结果：F(n, W)。
更新于：2016年4月6日
一篇对易理解的DP文章：从新手到专家