动态规划即Dynamic Programming，简称DP，无论是在日常生活还是在工程问题中都有着十分广泛的应用，比如最短路径问题，购物满减问题等等。 动态规划也是算法中较难的一个模块，而其中最大的问题在于如何确定状态以及状态转移方程，“状态”这一词在后面说明。 本文将从递归开始一步一步讲解到动态规划。

动态规划是一种将复杂问题拆分成相对简单的子问题并自下而上求解每个子问题最优解从而求解初始问题最优解的模型。 以下是维基百科对Dynamic Programming 的定义：

Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

与分治法以及递归操作一样，我们需要对问题进行拆分成子问题进行解决，不同在于递归操作将这一拆分过程展现出来并且当出现大量重复子问题时，递归依然会重新解决这些问题，而DP算法则是利用子问题之间的关系直接由子问题开始入手解决，每个子问题只计算一次，并且重复子问题不会再次计算。 这里也暗示了我们动态规划的使用前提之一，即拆分子问题之间有着某种关系且拆分过程会出现大量重复子问题。

在说自下而上之前，需要提及一下递归操作，递归操作是从当前需要求解的问题（顶）向下分解成子问题（下），一直分解到子问题满足止归条件，开始从下往上返回结果到当前需要求解的问题。 过程如下，从求解问题向其子问题分解推进，即为自顶而下。

自下而上则是一个相反的过程，不从求解问题出发，而是从求解问题的子问题出发，一步一步向上推进到顶端需要求解的问题。 以计算10由多少个１组成为例 自顶而下可以理解为: 10 = 1 + 9, 9 = 1 + 8, … 2 = 1 + 1,　 于是计算出２由两个１组成，３由１个１和１个２组成即１个１＋２个１=３个１…

自下而上则理解为: 1 + 1 = 2, 1 + 2 = 1 + 1 + 1 = 3 … 1+ 9 = 1 + 1 + … + 1 = 10 虽然这个例子很简单，但是从其中理解自下而上与自顶而下的区别还是比较容易的，即相当于去除了子问题分解的步骤，直接从子问题倒推到需求解问题。 当然也可以看出其实我们的子问题分解步骤并没有真的舍去，正如前文所述，其实是找到了子问题之间存在的某种关系才从子问题倒推出需求解的问题。那么这一关系数学上我们称之为数列的递推公式在动态规划中称之为状态转移方程。那么以后的问题就是如何定义子问题的状态以及如何确定状态转移方程。

在自下而上的过程中，我们对于每个子问题都是求解其最优解，因此我们得到的最终要求解的问题当然也是全局最优解。

DP问题虽然因题而已，但是呢，在确定是否使用DP解决问题，以及解决问题所需要的步骤还是比较固定的，相信大家在多次练习之后就明白如何去解决这类问题，当然问题有难有简，多学习熟能生巧嘛。 走四定三是博主自己的一种称呼，意思是DP最基本可以按照四个步骤进行求解，等熟练之后如果确定三点即可直接写出动态规划。

走四，四个基本步骤(内心问问自己下面四个问题)：

定三，三个需要确定的点：

斐波那契数列是最经典且十分简单的一道DP运算题了。

剑指offer 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下： 　　F(0) = 0, F(1) = 1 　　F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 示例 1： 　　输入：n = 2 　　输出：1 示例 2： 　　输入：n = 5 　　输出：5

走1: 能递归吗？肯定可以呀，上图

走2: 有大量重复子问题吗？当然有，比如第三个房屋如果偷，那么跳到第五个房间进行计算，然而当第四个房间不偷，同样也会跳到第五个房间进行计算。 走3: 备忘录带上，查小本本啦！

走4: 动态规划，当然可以，放到定三一起分析。

定三：当然此处我是做了空间优化，所以只使用了三个变量 首先，确定了肯定有重复子问题的出现 ＝> 定1 其次，状态量确定dp0代表着前一房屋不偷到该房屋后所得金额，dp1代表着前一房屋偷了到该房屋不偷所得金额，dp则取其中最大值最为求解结果，若此时处于第i屋，那么根据问题分析则dp = max{dp0 + nums[i], dp1} ＝> 定2 最后，最底层初始值三者皆为0 ＝> 定3