Summary

1.动态规划与divided conquer的区别：

dynamic programming（记忆化搜索）有记忆，divided conquer无记忆做重复计算。

2.什么时候用动态规划：

1> 求最大值/最小值

2> 判断方案是否可行

3> 统计方案个数

是极有可能用动态规划求解的

3.什么情况下不使用动态规划？

1>求出具体的方案而不是方案个数(一定不用)：

http://www.lintcode.com/problem/palindrome-partitioning/

2>输入的数据是一个集合而不是一个序列

http://www.lintcode.com/problem/longest-consecutive-sequence/

3>暴力算法的复杂度已经是多项式级别

动态规划擅长与优化指数级别复杂度(2^n,n!)到多项式级别复杂度(n^2,n^3)

不擅长优化n^3到n^2

4.动态规划四要素：

状态 State

• 灵感，创造力，存储小规模问题的结果

方程 Function

• 状态之间的联系，怎么通过小的状态，来算大的状态

初始化 Initialization

• 最极限的小状态是什么, 起点

答案 Answer

• 最大的那个状态是什么，终点

5.(比较)递归三要素：

定义（状态）

• 接受什么参数

• 做了什么事

• 返回什么值

扒皮（方程）

• 如何将参数变小

出口（初始化）

• 什么时候可以直接 return

6.坐标型动态规划

初始一个二维的动态规划时就去初始他的第0行和第0列。

• state:

• f[x] 表示我从起点走到坐标x……

• f[x][y] 表示我从起点走到坐标x,y……

• function: 研究走到x,y这个点之前的一步

• initialize: 起点

• answer: 终点

如果没有行走方式还可以使用动态规划吗？--不可以

Reason：有对前面的依赖关系。-->依赖关系出现了环状依赖-->不能使用动态规划-->

1)如果步数有限制可以使用动态规划，把步数放进状态中f[k][i][j]由f[k-1][i][j]得来，如键盘组合(Google)

2)有方向一直增减也可以用动态规划。

-----------------------------------------------------------------------------------------------

本文有视频版： 动态规划框架套路详解

这篇文章是我们公众号半年前一篇 200 多赞赏的成名之作 动态规划详解 的进阶版。由于账号迁移的原因，旧文无法被搜索到，所以我润色了本文，并添加了更多干货内容，希望本文成为解决动态规划的一部「指导方针」。

动态规划问题（Dynamic Programming）应该是很多读者头疼的，不过这类问题也是最具有技巧性，最有意思的。本书使用了整整一个章节专门来写这个算法，动态规划的重要性也可见一斑。

本文解决几个问题：

动态规划是什么？解决动态规划问题有什么技巧？如何学习动态规划？

刷题刷多了就会发现，算法技巧就那几个套路，我们后续的动态规划系列章节，都在使用本文的解题框架思维，如果你心里有数，就会轻松很多。所以本文放在第一章，来扒一扒动态规划的裤子，形成一套解决这类问题的思维框架，希望能够成为解决动态规划问题的一部指导方针。本文就来讲解该算法的基本套路框架，下面上干货。

首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。

既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。

动态规划这么简单，就是穷举就完事了？我看到的动态规划问题都很难啊！

首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」，才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，我来提供我研究出来的一个思维框架，辅助你思考状态转移方程：

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

按上面的套路走，最后的结果就可以套这个框架：

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

下面通过斐波那契数列问题和凑零钱问题来详解动态规划的基本原理。前者主要是让你明白什么是重叠子问题（斐波那契数列没有求最值，所以严格来说不是动态规划问题），后者主要举集中于如何列出状态转移方程。