1. 由一个例子说开： 斐波那契（fibonacci）数列

斐波那契数列是由0和1开始，之后的数就是前两个数的和。
首几个费波那契系数是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
那我们如何用计算机来生成这些数呢，也就是说，求斐波那契数列第n位的值。
很简单，用递归就可以了：

# 自上而下地递归
def fib(n):
    if n in [0,1]:
        return n
    return fib(n-1) + fib(n-2)
    
print(fib(10))

输出： 55

结果没有问题，接下来看一下递归性能如何。

性能测试

写个简单的计时的测试代码：

import time
n = 40
tic = time.clock()
res = fib(n)
toc = time.clock()
print('fib({}) = {}'.format(n,res))
print('runtime: {}s '.format(toc-tic))

我们看下n=10的结果：

fib(10) = 55
runtime: 2.4462208330078283e-05s 

再看下 n=40 时的结果：

fib(40) = 102334155
runtime: 40.73219172568648s 

我们发现：当n变大时，这段递归代码用时变得很久，而且性能是急剧下降。这是为什么呢？

原因分析

拿fib(5)来举例，要计算fib(5)，得知道fib(4)的值，要计算fib(4)的值，又得知道fib(3)的值，以此类推，直到递归到底时，fib(0)=0。下图是个fib(5)求解的展开图，可以看到，这里面有很过的重复计算，比如浅粉色框框住的fib(2)就重复计算了三次，可想而知当n很大时，这些重复计算的次数将呈指数上升，这就是递归效率不高的原因——重叠子问题。

---

2. 记忆化搜索

改进方法就是，将计算过的fib()值存储下来，下次用到直接查就行，这种方法叫记忆化搜索。
于是在递归代码的基础上可以很轻松地改写成记忆化搜索，代码如下：

# 记忆化搜索：自上而下地求解
def fib_memo(n):
    def fib(n):
        if n in [0,1]:
            return n
        # 如果memo数组中没有计算过fib(n)，则需计算一下并存到memo[n]中
        if memo[n] == -1:
            memo[n] = fib(n-1) + fib(n-2)
        return memo[n]

    memo = [-1 for i in range(n+1)]  # memo[0...n]中所有元素初始值为-1，表示未计算
    return fib(n)

fib(40)的测试结果：

fib(40) = 102334155
runtime: 2.4746652798057767e-05s 

经过简单的记忆化改造，效率由 40.7s 提升到了 0.0000247s ！
记忆化搜索本质还是一种递归，只是用额外的变量来存储中间值而已，属于典型的空间换时间的方式。由于递归是一种自顶向下的方式，所以记忆化搜索也是一种自顶而下的搜索方法，即计算顺序是

   fib(n) → fib(n-1) → fib(n-2) → ... → fib(1) → fib(0)

最后再从fib(0)一路回溯给fib(n)，done！

那么可不可以自底向上地算出斐波那契数列呢？当然有啊，这就是接下来要隆重请出的动态规划。

---

3. 动态规划（Dynamic Programming，DP）

思路很简单，知道了 fib(0) 和 fib(1)，就可以相加得fib(2)，fib(1)+fib(2)又得fib(3)，依次类推直到 fib(n)。自底向上的求解过程：

   fib(0) → fib(1) → fib(2) → ... → fib(n-1) → fib(n)

没错，这也极其符合人的直观感觉，看着很舒服很顺眼。
于是很容易写出代码：

# 动态规划：自下而上地解决问题
def fib(n):
    memo = [-1 for i in range(n+1)]
    memo[0] = 0
    memo[1] = 1
    for i in range(2,n+1):
        memo[i] = memo[i-1] + memo[i-2]
    
    return memo[n]

看下测试结果：

fib(40) = 102334155
runtime: 1.6782212696853094e-05s 

0.0000167s 比记忆化搜索的 0.0000247s 又提高了一丢丢，这主要是因为记忆化搜索中多出了反复递归的开销。

最优子结构

其实fib数列不是重点，重点是这个：这里面fib(2)是fib(3)的子问题，fib(3)又是fib(4)的子问题，以此类推，所以这是一个通过子问题推得原问题的过程。我们可以把上面的过程总结为这句话：通过求子问题的最优解，可以获得原问题的最优解。
这里的子问题称为最优子结构。
好，接下类引出动态规划的定义：

将原问题拆解成若干个子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

好，介绍完毕。

总结一下这几个解法：

在递归问题中如果存在重叠子问题，那么就可以进行以下两种改造：

1. 自顶而下地解决问题：记忆化搜索
2. 自底而上地解决问题：动态规划
   

几个例题

LeetCode 70 Climbing Stairs

解析：要爬到n阶台阶，有 ①从n-1阶再爬一阶到达 ②也可从n-2阶再爬2阶到达，这两种方式，所以爬到n阶的方法数等于爬到n-1阶的方法数与爬到n-2的方法数的和。接下来，n-1阶的方法数也等于n-2阶的加上n-3阶的，以此类推直到爬1阶和爬0阶。所以，这个问题本质就是一个fibonacci数列的求解！ 而且这里面也存在很多重复计算的子块，例如下图蓝色子块。同上面的代码一样，这个问题完全可以用原生的递归方法、记忆化搜索和动态规划求解的。

LeetCode上 其他相似的例题：

---

4. 动态规划的核心：状态与状态转移方程

前面我们将动态规划描述为一种 通过求子问题的最优解，从而求得原问题的最优解 的方法，那么有人可能会问了：

1. 如何将原问题切分成子问题？
2. 又怎么将子问题的解延伸回原问题，也就是说子问题和原问题是怎么连接起来的？

对于问题1，如何切分子问题，在DP中被称为状态的定义，其中子问题被称为状态。
对于问题2:，如何从子问题到原问题，在DP被称为状态转移方程。

这两个东西才是动态规划的核心。

到底是怎么回事，直接拿LeetCode上两个例子说话：

LeetCode 343 Integer Break

解析：

1. 我们定义 v[n] 分割正数n的最大乘积 ，这是状态的定义。
2. 每次将n分解为两个数的和，如：1+(n-1), 2+(n-2), 3+(n-3)…，对于每一种分割 i+(n-i)，最大乘积 v[n] 的来源于 i 和 n-i 的乘积 和 i 和 v[n-i] 的乘积 中较大的那个，而最终的最大v[n]是在所有 1<=i<=n上最大的那个，即v[n] = max( i×(n-i), i×v[n-i] ) for 1<=i<=n-1 ，这就是从v[n-1] 到 v[n] 的状态转移方程。
3. 这里存在重叠子问题，如下图中蓝块。
   
   思路： 递归、记忆化搜索、动态规划

1. 状态定义： v[n] 分割正数n的最大乘积
2. 状态转移： v[n] = max( i×(n-i), i×v[n-i] ) for 1<=i<=n-1

代码
我将递归、记忆化搜索和动态规划三种方法放在了一个类中：

class Solution:
    def integerBreak_rec(self, n):
        """
        :type n: int
        :rtype: int
        原生的递归方法：效率低
        """
        def breakInteger(n):
            if n==1:
                return 1
            res = -1
            for i in range(1,n):
                # n = i + (n-i)
                res = max( res, i*(n-i), i*breakInteger(n-i) )
            return res

        return breakInteger(n)

    def integerBreak_memo(self, n):
        """
        :type n: int
        :rtype: int
        第一种改进： 自上而下的记忆化搜索
        """
        def breakInteger(n):
            if n==1:
                return 1
            if memo[n] != -1:
                return memo[n]
            res = -1
            for i in range(1,n):
                # n = i + (n-i)
                res = max( res, i*(n-i), i*breakInteger(n-i) )
            memo[n] = res
            return res

        assert n>=2
        memo = [-1 for i in range(n+1)]
        return breakInteger(n)

    def integerBreak_dp(self, n):
        """
        :type n: int
        :rtype: int
        第二种改进：自底向上动态规划
        """
        assert n>=2
        memo = [-1 for i in range(n+1)]

        memo[1] = 1
        for i in range(2,n+1):
            for j in range(1,i):
                memo[i] = max( memo[i], j*(i-j), j*memo[i-j] )
                
        return memo[n]
     
if __name__ == '__main__':      
    n = Solution().integerBreak_dp(10)
    print(n)

LeetCode上与此题相似的题目：

• 279 Perfect Squares
  给定一格正整数n，寻找最少的完全平方数，使他们的和为n。
• 91 Decode Ways
  数字字符串的解析
• 62 Unique Paths
  机器人从m×n的矩阵左上角出发到达右下角（每次只能向右或向下），共有多少种路径？
• 63 Unique Paths II
  （接上题）若矩阵中含有障碍物，此时共有多少种路径？

LeetCode 198 House Robber

小偷洗劫一条街上的所有房子，每个房子有不同价值的把宝物，但不能连续抢劫俩相邻房子。求最多可以偷到多少宝物？

暴力解法

检查所有房子的组合，对每一个组合，检查是否有相邻的房子，如果没有，记录其价值，找最大值。
时间复杂度: O( (2^n)*n )
这个方法效率非常之低。

动态规划

考虑如下结构

"""
198. House Robber

转态定义：考虑偷取[x...n)范围里的房子
状态转移方程：
            f(0) = max{ v(0)+f(2),
                        v(1)+f(3),
                        v(2)+f(4),
                        ...
                        v(n-3)+f(n-1),
                        v(n-2),
                        v(n-1)}  
"""
class Solution:
    def rob_rec(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        递归方法
        """
        # 考虑抢劫nums[index:]范围内的所有房子
        def tryRob(index)：
            if index >= len(nums):
                return 0
            res = 0
            for i in range(index,len(nums)):
                res = max( res, nums[i]+tryRob(i+2) )
            return res

        return tryRob(0)

    def rob_memo(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        记忆化搜索
        """
        # 考虑抢劫nums[index:]范围内的所有房子
        def tryRob(index)：
            if index >= len(nums):
                return 0
            if memo[index] != -1:
                return memo[index]

            res = 0
            for i in range(index,len(nums)):
                res = max( res, nums[i]+tryRob(i+2) )
            memo[index] = res
            return res

        # memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
        memo = [-1 for i in range(n)]
        return tryRob(0)

        
    def rob_dp(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        动态规划法
        """
        n = len(nums)
        if n == 0:
            return 0
        
        # memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
        memo = [-1 for i in range(n)]
        memo[n-1] = nums[n-1]
        
        for i in range(n-2,-1,-1):
            # memo[i]
            for j in range(i,n):
                if j<n-2:
                    memo[i] = max(memo[i],nums[j]+(memo[j+2]) 
                else:
                    memo[i] = max(memo[i],nums[j]) # 末尾两个元素只能是自己
                
        return memo[0]
        
        
if __name__ == '__main__':          
	nums = [2,7,9,3,1]
	res = Solution().rob_dp(nums)   
	print(res)

LeetCode上与此题相似的题目：

• 213 House Robber II
  此处将街道改为环形街道，即最后一个元素和第一个元素为邻居。求窃得财产的最大值。
• 337 House Robber III
  此处将街道给为小区，小区是二叉树结构，即不能同时选择相邻节点。
• 309 Best Time to Buy and Sell Stock with Cooldown
  股票买卖时机的选择，使利润最大化。

---

5. 动态规划经典应用：背包问题

在动态规划中，有类非常经典的问题称为0-1背包问题。有一个背包，容量是C，现有那种不同的物品，编号为0…n-1
，其中每一件物品重量为w(i),价值为v(i)。问可以向包中放哪些物品，使得在不超过背包容量的基础上，物品总价值最大。

三种解法

暴力解法：每一件物品都可以放进或者不放进，遍历所有可能性。 时间复杂度O((2^n)*n)。
贪心算法：优先放入平均价值最大的物品，结果只是近似解，而不是最优解。
动态规划：

状态： F(n,C) 考虑将n个物品放进容量为C的背包，使得价值最大。(这里约束条件为n和C)
状态转移方程： F(i,C) = max( F(i-1,C), v(i)+F(i-1,C-w(i)) )
对应 1.不放入第i个物品 2.放入第i个物品 这两种状态中值最大的那个。

背包问题动态规划解法的实现及优化

时间复杂度为O(nC)已经几乎没有优化空间了，但是可以从空间复杂度上进行优化。

1. 动态规划解法: n行版
   原始动态规划，建立一个n行C+1列的矩阵 memo[n-1][C+1]
   时间复杂度：O(nC)
   空间复杂度：O(nC)

2. 动态规划解法: 两行版
   改进1：由于第i行元素只依赖于第i-1行元素。理论上，memo只需要保证两行元素。
   空间复杂度 O(2C)=O( C)

3. 动态规划解法： 一行版
   改进2：由于某位置的元素只依赖于上一行的对应位置和上一行的左侧元素。所以可以从右边开始更新，这样memo只需一行就可以完成。
   空间复杂度 O( C)

背包问题的变种

• 多重背包问题：每个物品不止1个，有num(i)个
• 完全背包问题：每个物品可以无限使用
• 多维费用背包问题：要考虑物品的体积和重量两个维度（原问题上增加一个约束条件，memo数组变为三维即可）
• 物品间加入更多约束：物品间可以相互排斥；也可以相互依赖

背包问题实例

416 Patition Equal Subset Sum 分割等和子集

典型的背包问题：在n个物品中选出一定物品，填满sum/2的背包
与原背包问题不同的是：我们不需要物品价值最大，目标是能填满。或者也可以理解为物品价值均为1。

LeetCode上与此题相似的题目：

• 322 Coin Change
  给定不同面值的硬币，问需要多少硬币（可反复使用），可以凑成指定的金额？
• 377 Combination Sum IV
  给定一整数数组（无重复数字，但数字可重复使用），问有多少种可能，使用这个数组中的数字，凑成一个指定的整数target。
• 474 Ones and Zeros
• 139 Word Break
  判断字符串数组中可否有不同字符串收尾相连组成target字符串。
• 494 Target Sum
  给定非0数字数组，在这些数前面加上+或-，使其结果为给定的整数S。

---

6. 动态规划应用： 最长上升子序列（LIS）

300 Longest Increasing Subsequence

给定一整数序列，求其中的最长上升子序列的长度。

• 方法1：动态规划解法
  1. 状态定义： LIS(i) 表示以第i个数字为结尾的最长上升子序列的长度。即表示[0…i]范围内，选择数组nums[i] 可以获得的最长上升子序列的长度
  2. 状态转移： LIS(i) = max( 1+LIS(j) if nums[i]>nums[j] for j<i )
  时间复杂度O(n^2)
• 方法2：二分搜索法
  这里不做介绍。
  时间复杂度O(nlogn)

LeetCode上与此题相似的题目：

• 376 Wiggle Subsequence
  求最长轮流交替子序列

最长公共子序列: LCS问题

给出两个字符串S1和S2，求这两个字符串的最长公共子序列的长度。
状态定义：

LCS(m,n) 是S1[0…m]和S2[0…n]的最长公共子序列的长度。

转移方程：

1. S1[m] == S2[n]： LCS(m,n) = 1+ LCS(m-1,n-1)
2. S1[m] != S2[n]： LCS(m,n) = max(LCS(m-1,n),LCS(m,n-1))

7. 关于动态规划的其他：

• 动态规划其实相当常见，譬如 dijkstra单源最短路径算法也是动态规划

  状态定义： shortestPath(i)为从start到i的最短路径长度
  状态转移： shortestPath(i) = min( shortestPath(i) + w(a->i))

• 动态规划是一个非常大的问题范畴，因为它不仅他可以解决的问题是非常灵活的，还因为它是公认的在算法设计上艺术含量非常高的算法，因为动态规划似乎没有一个固定的套路。
• LeetCode上更多关于动态规划的问题，找dp标签的题。
• 单论面试，面试中动态规划考察较少，更多的是考察更基础的问题，所以可以相对放松对LeetCode上动态规划题目的要求。

8. 如何用动态规划给出具体的解：返回去找

例1： 300. 最长上升子序列。
例2： 0-1背包问题

References：
非常好的动态规划总结，DP总结
背包问题的总结
动态规划（dp） 之 状态转移方程

动态规划的基本原理

能用动态规划解决的问题的特点

• 问题具有最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。

• 无后效性：当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取那种手段、哪条路径演变到当前的这若干个状态无关。事实上，不满足无后效性的问题分解是写不出状态转移方程的。不过这也与我们分划问题涉及状态的艺术有关。

动态规划解题的一般思路

• 将原问题分解为n个子问题：将原问题分解为若干个子问题，子问题和原问题形式相同或者类似，只不过规模变小。当子问题全都解决时，原问题即解决。子问题的解一旦求出就被保存，所以每个子问题只需要求解一次。

• 确定状态：用动态规划解题，经常碰到的情况是，K个整形变量能构成一个状态，我们用一个K维的数组来存储各个状态的值。注意这里的值并不一定是一个数，而可能是结构体等。一个状态下的值通常是一个或者多个子问题的解

• 确定一些初始状态（边界条件）的值

  • 如果使用记忆化搜索，即设置递归出口，
  • 如果使用递推，就需要将这些值填入dp数组

• 确定状态转移方程：求出不同状态之间是如何迁移的，即如何从一个或者多个值已知的状态，求出另一个状态的值。状态的迁移通常可以用递推公式表示，该公式就是状态迁移方程。

具体实现

• 记忆化搜索

  • 直接按照递归函数的思路完成编写，只是在函数的头部增加快捷返回出口，函数return前存储值。
  • dp数组：递归函数有n个参数，就定义一个n维的数组，数组的下标最大值是递归函数参数的取值范围
  • 也就是说，我们把每一种参数对应的值都开一个空间存起来。

• 递推

  • 根据我们的递推公式来判断循环递推的方向。如果递推公式涉及的元素是不断增大的，那么就从小开始递推不断增大，反之则从大开始不断减小

    比如 $dp[r][j]=max(dp[r+1][j],dp[r+1][j+1])+num[r][j];$

    这个递推公式涉及的元素r、j都不断增大，那么我们就应该从小到大递推

  • 确定递推的边界条件。最初始的一些值我们需要提前在dp数组中初始化好，同时还要设置一些递推的非法出口的值。非法出口的设置需要保证：永远不可能用到这个出口来更新某个dp，故而我们应使用反向意义来设置非法出口

    非法出口类同于递归中出现超出范围、显然不再可能可以完成任务的参数的情况的return

    反向意义：例如我们求最小值，非法出口就应定义为99999999

  • 在递推中，当我们在求$dp[r][j]$时，我们必须已经求出了所有r、j之前的dp值，故而判断递推的方向和边界条件非常重要

  • 用一个N层循环来递推，N为dp数组的维数，从边界值开始，逐步填充数组，前一个阶段的解，为后阶段的求解提供有用的信息

  • 使用递推的时候虽然快，但是要考虑的东西却很多很多，有一些局部细节和临界条件的考虑非常重要，有时候记忆化搜索能AC递推却WA就是因为有一些极限情况没有考虑到

0. intro　　
很有意思的问题。以往见过许多教材，对动态规划（DP）的引入属于“奉天承运，皇帝诏曰”式：不给出一点引入，见面即拿出一大堆公式吓人；学生则死啃书本，然后突然顿悟。针对入门者的教材不应该是这样的。
现在，我们试着自己来一步步“重新发明”DP。
1.从一个生活问题谈起　　
先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。　　
依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推。在这种策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。　　
这种策略称为“贪心”：假设我们面对的局面是“需要凑出w”，贪心策略会尽快让w变得更小。能让w少100就尽量让它少100，这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明，贪心策略是正确的。　　
但是，如果我们换一组钞票的面值，贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出15的时候，贪心策略会出错：　　15=1×11+4×1 （贪心策略使用了5张钞票）　　15=3×5 （正确的策略，只用3张钞票）　　
为什么会这样呢？贪心策略错在了哪里？　　
鼠目寸光。　　
刚刚已经说过，贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。　　
在这里我们发现，贪心是一种只考虑眼前情况的策略。　　那么，现在我们怎样才能避免鼠目寸光呢？　　
如果直接暴力枚举凑出w的方案，明显复杂度过高。太多种方法可以凑出w了，枚举它们的时间是不可承受的。我们现在来尝试找一下性质。　　
重新分析刚刚的例子。w=15时，我们如果取11，接下来就面对w=4的情况；如果取5，则接下来面对w=10的情况。我们发现这些问题都有相同的形式：“给定w，凑出w所用的最少钞票是多少张？”接下来，我们用f(n)来表示“凑出n所需的最少钞票数量”。　　
那么，如果我们取了11，最后的代价（用掉的钞票总数）是多少呢？　　
明显 ，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。　　
依次类推，马上可以知道：如果我们用5来凑出15，cost就是 。　　
那么，现在w=15的时候，我们该取那种钞票呢？当然是各种方案中，cost值最低的那一个！

• 取11：
• 
• 取5：
• 
• 取1：

显而易见，cost值最低的是取5的方案。我们通过上面三个式子，做出了正确的决策！　　
这给了我们一个至关重要的启示—— f(n)只与f(n-1),f(n-5),f(n-11) 相关；更确切地说:f(n)=min{f(n-1),f(n-5),f(n-11)}+1;
这个式子是非常激动人心的。我们要求出f(n)，只需要求出几个更小的f值；既然如此，我们从小到大把所有的f(i)求出来不就好了？注意一下边界情况即可。代码如下：

我们以 的复杂度解决了这个问题。现在回过头来，我们看看它的原理：f(n)只与f(n-1),f(n-5),f(n-11)的值有关。我们只关心f（w） 的值，不关心是怎么凑出w的。　　
这两个事实，保证了我们做法的正确性。它比起贪心策略，会分别算出取1、5、11的代价，从而做出一个正确决策，这样就避免掉了“鼠目寸光”！　　
它与暴力的区别在哪里？我们的暴力枚举了“使用的硬币”，然而这属于冗余信息。我们要的是答案，根本不关心这个答案是怎么凑出来的。譬如，要求出f(15)，只需要知道f(14),f(10),f(4)的值。其他信息并不需要。我们舍弃了冗余信息。我们只记录了对解决问题有帮助的信息——f(n).我们能这样干，取决于问题的性质：求出f(n)，只需要知道几个更小的f©。我们将求解f©称作求解f(n)的“子问题”。　　
这就是DP（动态规划，dynamic programming）.　　
将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。思考题：请稍微修改代码，输出我们凑出w的方案。

2 几个简单的概念**【无后效性】**　
一旦f(n)确定，“我们如何凑出f(n)”就再也用不着了。　　
要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。　　
“未来与过去无关”，这就是无后效性。　　
（严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。）
【最优子结构】　　
回顾我们对f(n)的定义：我们记“凑出n所需的最少钞票数量”为f(n).　　
f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的最优解，我们即可算出w=15的最优解。　　
大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。　　
引入这两个概念之后，我们如何判断一个问题能否使用DP解决呢？　　
能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。

3. DP的典型应用：DAG最短路　　
问题很简单：给定一个城市的地图，所有的道路都是单行道，而且不会构成环。每条道路都有过路费，问您从S点到T点花费的最少费用。

这个问题能用DP解决吗？我们先试着记从S到P的最少费用为f§.想要到T，要么经过C，要么经过D。从而

好像看起来可以DP。现在我们检验刚刚那两个性质：
　　- 无后效性：对于点P，一旦f§确定，以后就只关心f§的值，不关心怎么去的。
　　- 最优子结构：对于P，我们当然只关心到P的最小费用，即f§。如果我们从S走到T是
　　
　　那肯定S走到Q的最优路径是
　　
对一条最优的路径而言，从S走到沿途上所有的点（子问题）的最优路径，都是这条大路的一部分。这个问题的最优子结构性质是显然的。
既然这两个性质都满足，那么本题可以DP。式子明显为：
其中R为有路通到P的所有的点， w_{R→P} 为R到P的过路费。
代码实现也很简单，拓扑排序即可。

4. 对DP原理的一点讨论【DP的核心思想】
DP为什么会快？　
无论是DP还是暴力，我们的算法都是在可能解空间内，寻找最优解。　　
来看钞票问题。暴力做法是枚举所有的可能解，这是最大的可能解空间。　　DP是枚举有希望成为答案的解。这个空间比暴力的小得多。　　
也就是说：DP自带剪枝。　　
DP舍弃了一大堆不可能成为最优解的答案。譬如：　　
15 = 5+5+5 被考虑了。　　
15 = 5+5+1+1+1+1+1 从来没有考虑过，因为这不可能成为最优解。　　
从而我们可以得到DP的核心思想：尽量缩小可能解空间。　　
在暴力算法中，可能解空间往往是指数级的大小；如果我们采用DP，那么有可能把解空间的大小降到多项式级。　　
一般来说，解空间越小，寻找解就越快。这样就完成了优化。
【DP的操作过程】　　
一言以蔽之：大事化小，小事化了。　　
将一个大问题转化成几个小问题；　　
求解小问题；　　
推出大问题的解。

【如何设计DP算法】　　
下面介绍比较通用的设计DP算法的步骤。　　
首先，把我们面对的局面表示为x。这一步称为设计状态。　　
对于状态x，记我们要求出的答案(e.g. 最小费用)为f(x).我们的目标是求出f(T).找出f(x)与哪些局面有关（记为p），写出一个式子（称为状态转移方程），通过f§来推出f(x).
【DP三连】　　
设计DP算法，往往可以遵循DP三连：　　
我是谁？ ——设计状态，表示局面　　
我从哪里来？　　
我要到哪里去？ ——设计转移　　
设计状态是DP的基础。接下来的设计转移，有两种方式：一种是考虑我从哪里来（本文之前提到的两个例子，都是在考虑“我从哪里来”）；另一种是考虑我到哪里去，这常见于求出f(x)之后，更新能从x走到的一些解。这种DP也是不少的，我们以后会遇到。　　
总而言之，“我从哪里来”和“我要到哪里去”只需要考虑清楚其中一个，就能设计出状态转移方程，从而写代码求解问题。前者又称pull型的转移，后者又称push型的转移。

5.例题：
最长上升子序列　　
最长上升子序列（LIS）问题：给定长度为n的序列a，从a中抽取出一个子序列，这个子序列需要单调递增。问最长的上升子序列（LIS）的长度。
e.g. 1,5,3,4,6,9,7,8的LIS为1,3,4,6,7,8，长度为6。　　
如何设计状态（我是谁）？　　
我们记 f(x)为以 a(x) 结尾的LIS长度，那么答案就是 max{f（x）}。
状态x从哪里推过来（我从哪里来）？　　
考虑比x小的每一个p：如果 ，那么f(x)可以取f§+1.　　解释：我们把 接在 的后面，肯定能构造一个以 结尾的上升子序列，长度比以 结尾的LIS大1.那么，我们可以写出状态转移方程了：　　

至此解决问题。两层for循环，复杂度 .

从这个例题中可以看出，DP是一种思想，一种“大事化小，小事化了”的思想。带着这种思想，DP将会成为我们解决问题的利器。

这篇博客是我在知乎看到后感觉很好转载整理过来的，之前对dp还是有点懵，看完以后有种茅塞顿开的感觉，这篇文章是上海洛谷有限公司讲师阮行止老师的原创。