状态转移方程
1. 最大子序列和-leetcode53
给定一个整数数组nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
状态转移方程：v(i) = max(v(i-1) + num[i], num[i])
解释：这里为什么不是v(i) = max(v(i - 1) + nums[i] , v(i - 1))？如果这么写的话，有可能v[i]和 v[i - 1]是同一个子序且也不能实现是连续子序的要求。
2. 打家劫舍-leetcode198
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
状态转移方程：v(i) = max(v(i-2)+nums[i], v(i-1))
3
4
5
6
7
8
5. 三角形最小路径和(数塔问题)-leetcode120
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
分析：
在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。
从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。
所以第一步对第五层的8个数据，做如下四次决策：
如果经过第四层2，则在第五层的19和7中肯定是19；
如果经过第四层18，则在第五层的7和10中肯定是10；
如果经过第四层9，则在第五层的10和4中肯定是10；
如果经过第四层5，则在第五层的4和16中肯定是16；
经过一次决策，问题降了一阶。5层数塔问题转换成4层数塔问题，如此循环决策…… 最后得到1阶的数塔问题。
算法实现：首先利用一个二维数组data存储数塔的原始数据（其实我们只使用数组data一半的空间，一个下三角矩阵），然后利用一个中间数组dp存储每一次决策过程中的结果（也是一个下三角矩阵）。
初始化dp，将data的最后一层拷贝到dp中。dp[n][j] = data[n][j] (j = 1, 2, …, n)其中，n为数塔的层数。在动态规划过程汇总，我们有：
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + data[i][j]，
最后的结果保存在dp[0][0]中。
对于上面的数塔，我们的data数组如下：
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16
而我们的dp数组如下：
59
50 49
38 34 29
21 28 19 21
19 7 10 4 16
5. 背包问题I-lintcode92
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i](不可以将物品进行切割)
样例 1:
输入: [3,4,8,5], backpack size=10
输出: 9
样例 2:
输入: [2,3,5,7], backpack size=12
输出: 12
dp[j] = max(dp[j-A[i]] + A[i], dp[j])
6. 背包问题II-lintcode125
有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.问最多能装入背包的总价值是多大?
A[i], V[i], n, m 均为整数你不能将物品进行切分你所挑选的要装入背包的物品的总大小不能超过 m每个物品只能取一次
样例 1:
输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]
输出: 9
解释: 装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9
样例 2:
输入: m = 10, A = [2, 3, 8], V = [2, 5, 8]
输出: 10
解释: 装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10
dp[j] = max(dp[j-A[i]]+V[i], dp[j])
dp[i][j]=max{dp[i-1][j-A[i]]+V[i], dp[i-1][j]};
7. 背包问题III
给定n种具有大小 Ai和价值 Vi的物品(每个物品可以取用无限次)和一个大小为 m 的一个背包, 你可以放入背包里的最大价值是多少?
样例 :
给出四个物品, 大小为 [2, 3, 5, 7], 价值为 [1, 5, 2, 4], 和一个大小为 10 的背包. 最大的价值为 15.
dp[j] = max(dp[j], dp[j - 1], dp[j - A[k]] + V[k])
参考文献：
[2] https://blog.csdn.net/theonegis/article/details/45801201
