动态规划一般分为三类问题：
- 计数
-有多少种方式走到右下角
-有多少种方法选出k个数使得和是Sum - 最大最小值
-从左上角走到右下角路径的最大数字和
-最长上升子序列长度 - 存在性
-取石子游戏，先手是否必胜
-能不能选出k个数使得和是Sum
解题思路一般需要首先bottom-up然后top-down去设计。
例题：
给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.
样例
样例1
输入：
[1, 2, 5]
11
输出： 3
解释： 11 = 5 + 5 + 1
样例2
输入：
[2]
3
输出： -1
解题步骤如下（以样例1为例）：
- 确定状态。
研究最优策略的最后一步（最优策略中使用的最后一枚硬币(a_k)）、化成子问题（最少的硬币拼出更小的面值(11-a_k)）。 - 转移方程。
[dp[X]=min{ dp[X-1]+1,dp[X-2]+1,dp[X-5]+1 }
]
- 初始条件和边界条件。
$ dp[0] = 0 (，如果不能拼出Y， ) dp[Y] = INTMAX $ - 计算顺序。 利用好之前的计算结果。
$ dp[0], dp[1], dp[2]… $
动态规划经典题型
- 序列型。LintCode 515. https://www.lintcode.com/problem/paint-house/description
- 划分型。LintCode 512. https://www.lintcode.com/problem/decode-ways/description
- 坐标型。LintCode 76. https://www.lintcode.com/problem/longest-increasing-subsequence/description
序列型动态规划
这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的费用。
费用通过一个nx3 的矩阵给出，比如cost[0][0]表示房屋0染红色的费用，cost[1][2]表示房屋1染绿色的费用。
样例
样例 1:
输入: [[14,2,11],[11,14,5],[14,3,10]]
输出: 10
解释: 蓝 绿 蓝, 2 + 5 + 3 = 10
样例 2:
输入: [[1,2,3],[1,4,6]]
输出: 3
序列型动态规划的特点，是需要使用(dp[i])来表示前i个项目的最小数/方式数/可行性。
此题中，在设计动态规划的过程中，发现涂前N-1栋房子的最优策略中，需要知道房子N-2的颜色。如果只用(dp[N-1])，将无法区分。
解决方法：记录下房子N-2的颜色*在房子N-2是红/蓝/绿色的情况下，油漆前N-1栋房子的最小花费。
关键词为：序列+状态
划分型动态规划
有一个消息包含A-Z通过以下规则编码
'A' -> 1
'B' -> 2
...
'Z' -> 26
现在给你一个加密过后的消息，问有几种解码的方式
样例
样例 1:
输入: "12"
输出: 2
解释: 它可以被解码为 AB (1 2) 或 L (12).
样例 2:
输入: "10"
输出: 1
划分型动态规划的特点，是需要划分不同的条件来计算(dp[i])。
[dp[i] = dp[i-1] | S[i-1]可以对应一个字母 + dp[i-2] | S[i-2] S[i-1]可以对应一个字母
]
坐标型动态规划
以LintCode 76. Longest Increasing Subsequence为例，
给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。
样例
样例 1:
输入: [5,4,1,2,3]
输出: 3
解释:
LIS 是 [1,2,3]
样例 2:
输入: [4,2,4,5,3,7]
输出: 4
解释:
LIS 是 [2,4,5,7]
挑战
要求时间复杂度为O(n^2) 或者 O(nlogn)