我们之前学过分治，分治策略就是将原问题划分成n个规模较小独立的而结构和原问题相似的子问题，递归的求解子问题，然后合并结果得到原问题的解。
而dp的子问题不是独立的，而是重叠的，也就是各子问题包含公共的子子问题。我们不需要重复的求解公共的子子问题，而是对每个子子问题只求解一次，然后纪录下来。动态规划用于解决最优化问题，所以每个子问题也是最优解。
1.最大连续子段和（leetcode 53. Maximum Subarray）
状态：dp[i]表示以i为结尾的最大连续子段和
状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])
2.数字三角形问题，从顶部走到底部的最大和（poj 3176 ）
状态：dp[i][j]表示从顶部(0,0)走到(i,j)的最大和
状态转移方程：dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + map[i][j]
类似题目 leetcode 62. Unique Paths
3.最长上升子序列LIS（leetcode 300. Longest Increasing Subsequence）
状态：dp[i]表示以i为结尾的最长上升子序列长度
状态转移方程：dp[i] = max(dp[0], dp[1], ... dp[j])+1 （其中0<=j<i dp[i]>dp[j]）
4.最长公共子序列LCS（poj 1458）
状态：dp[i][j]表示a串中0～i和b串中0～j的子串的最长公共子序列长度
状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+(a[i] == b[j]))
5.01背包问题（poj 3624）
题目描述：有N件物品和一个容量为V的背包，第i件物品的费用是c[i]，价值是w[i]，问将哪些物品装入背包能使价值总和最大。每种物品仅有一件。
状态：dp[i][j]表示前i件物品放入容量为j的背包可以获得的最大价值
状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]] + w[i])
类似题目：leetcode 416. Partition Equal Subset Sum
1.滚动数组dp[2][V]
for(int i = 0; i < N; i++)
{
int id = i&1;
for(int j = 0; j <= V; j++)
{
dp[id][j] = max(dp[id^1][j], dp[id^1][j-c[i]]+w[i]);//伪代码，条件自己判断
}
}2.二维dp压缩成一维dp，去掉第一维，逆序推导dp[j]。
for(int i = 0; i < N; i++)
{
for(int j = V; j >= c[i]; j--)
{
dp[j] = max(dp[j], dp[j-c[i]] + w[i]);
}
}注意：初始化、边界条件
各种各样的dp......
dp是思维难度大于编程难度的算法。