前言
在上一篇文章动静布局的文章中，咱们先由 Fibonacci 例子引入到了动静布局中，而后借助兑换零钱的例子，剖析了动静布局最次要的三个性质，即：
- 重叠子问题
- 最优子结构
- 状态转移方程
然而动静布局远不止这么简略。
明天这篇文章，让咱们深刻动静布局，一窥动静布局的实质。
咱们既然要彻底搞清楚动静布局，那么一个不可避免的问题就是：
递归，贪婪，记忆化搜寻和动静布局之间到底有什么不同？
- 动静布局于递归 ：只是单纯的空间换工夫吗？ 并不是，斐波那切数列的例子很好的颠覆了这个观点。
- 动静布局于贪婪：只是贪婪的加强版吗？并不是，零钱兑换的例子同样颠覆了这个观点。
那么，动静布局的外围到底是什么？
要答复这个问题，咱们无妨先答复上面这个问题：
到底哪些问题适宜用动静布局即？怎么鉴定 DP 可解问题？
置信当咱们意识到哪些问题能够用 DP 解决，咱们也就天然找到了 DP 和其它算法思维的区别，也就是动静布局的外围。
动静布局外围
首先咱们要搞清楚，动静布局只实用于某一类问题，只是某一类问题的解决办法。
那么这“某一类问题”是什么问题呢？
聊这个之前咱们有必要略微理解下计算机的实质。
基于冯诺依曼体系结构的计算机实质上是一个状态机，为什么这么说呢？因为 CPU 要进行计算就必须和内存打交道。
因为数据存储在内存当中（寄存器和外盘性质也一样），没有数据 CPU 计算个空气啊？所以内存就是用来保留状态（数据）的，内存中以后存储的所有数据形成了以后的状态，CPU 只能利用以后的状态计算下一个状态。
咱们用计算机解决问题，无非就是在思考：如何用变量来贮存状态，以及如何在状态之间转移：由一些变量计算出另一些变量，由以后状态计算出下一状态。
基于这些，咱们也就失去了评判算法的优劣最次要的两个指标：
- 空间复杂度：就是为了反对计算所必须存储的状态
- 工夫复杂度：就是初始状态到最终状态所需多少步
如果上述表述还不是很分明，那咱们还是举之前 Fibonacci 的例子来说：
- 要计算以后 f(n)，只须要晓得 f(n - 1) 和 f(n - 2).
即：
- 要计算以后状态 f(n)，只须要计算状态 f(n - 1)和 f(n -2).
也就是说以后状态只与前两个状态无关，所以对于空间复杂度：咱们只需保留前两个状态即可。
这也就很好的解释了为什么动静布局并不是单纯的空间换工夫，因为它其实只跟状态无关。
由一个状态转移到另一状态所需的计算工夫也是常数，故线性减少的状态，其总的工夫复杂度也是线性的。
以上便是动静布局的外围，即：
状态的定义及状态之间的转移（状态方程的定义）。
那么如何定义所谓的“状态”和“状态之间的转移”呢？
咱们引入维基百科的定义：
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.
那就是通过拆分问题，定义问题状态和状态之间的关系，使得问题可能以递推（或者说分治）的形式去解决。
纸上谈来终觉浅，下边咱们再来看一道同样十分经典的例题。
最长递增子序列
这是 LeetCode 第 300 题。
给定一个数列，长度为 N，求这个数列的最长回升（递增）子数列（LIS）的长度.
示例 1：
输出：nums = [10,9,2,5,3,7,101,18]输入：4解释：最长递增子序列是 [2,3,7,101]，因而长度为4示例 2：
输出：nums = [0,1,0,3,2,3]输入：4解释：最长递增序列是 [0,1,2,3]，因而长度为4
咱们如何进行状态的定义及状态间转移的定义呢？
一、状态的定义
首先咱们应该进行问题的拆分，即进行这个问题子问题的定义。
所以，咱们从新定义一下这个问题：
给定一个数列，长度为 N，
设 F~k~为：给定数列中第 k 项结尾的最长递增子序列的长度
求 F~1~到 F~N~的最大值
是不是上边这个定义与原问题一样？
显然二者等价，不过显著第二种定义的形式，咱们找到了子问题。
对于 F~k~来讲，F~1~到 F~k-1~都是 F~k~的子问题。
上述新问题的 F~k~ 就叫做 状态。
F~k~为数列中第 k 项结尾的 LIS 的长度 即为状态的定义。
二、状态转移方程的定义
状态定义好之后，状态与状态之间的关系式，就叫状态转移方程。
此题以 F~k~的定义来说：
设 F~k~为：给定数列中第 k 项结尾的最长递增子序列的长
思考，状态之间应该怎么转移呢？
还记得咱们之前说的拆分问题不，在这里同样咱们能够沿用这一招，即拆分数据。
如果数列只有一个数呢？那咱们应该返回 1(咱们找到了状态边界状况)。
那么咱们能够写出以下状态转移方程：
F~1~ = 1
F~k~ = max ( F~i~ + 1 | i ∈（1，k-1）)（k > 1）
即：以第 k 项结尾的 LIS 的长度是：max { 以第 i 项结尾的 LIS 长度 + 1 }, 第 i 项比第 k 项小
大家了解下，是不是这么回事～
回顾一下咱们是怎么做的？
- 咱们通过拆分问题进行了问题（子问题）的重定义（状态的定义）；
- 通过状态的定义，再联合状态的边界状况，咱们写出了状态与状态之间转移即状态转移方程的定义。
写出了状态转移方程，能够说到此，动静布局算法外围的思维咱们曾经表达出来了。
剩下的只不过是用记忆化地求解递推式的办法来解决就行了。
上面咱们尝试写出代码。
代码
首先咱们定义 dp 数组：
int[] dp = new int[nums.length];（留神这里 dp 数组的大小跟上一篇文章兑换零钱的例子有一丢丢不同，即这里没有+1，大家能够再点击这里看下上一篇文章认真了解一下。）
那么这里 dp 数组的含意就是：
dp[i] 保留的值即是给定数组 i 位之前最长递增子序列的长度。
那么咱们的初始状态是什么呢？
咱们晓得状态的边界状况为：
F~1~ = 1
- 即如果数据只有一位那么应该返回 1；
- 当数据个数 > 1 时，如果整个数列没有呈现第二个递增的数，那么同样返回 1.
所以，初始状态咱们给 dp 数组每个地位都赋为 1.
Arrays.fill(dp, 1);而后，咱们从给定数组的第一个元素开始遍历，即写出外层的 for 循环：
for(int i = 0; i < nums.length;i++){ ......}当咱们外层遍历到某元素时，咱们怎么做呢？
咱们得找一下，在这个外层元素之前，存不存在比它小的数，如果存在，那么咱们就更新此外层元素的 dp[i]
如果某元素之前有比它小的数，那么这不就形成了递增子序列了吗？
因而咱们能够写出内层 for 循环：
for (int j = 0; j < i; j++) { //如果后面有小于以后外层nums[i]的数，那么就令以后dp[i] = dp[j] + 1 if (nums[j] < nums[i]) { //因为以后外层nums[i]前边可能有多个小于它的数，即存在多种组合，咱们取最大的一组放到dp[i]里 dp[i] = Math.max(dp[i], dp[j] + 1); }}两层循环完结时，dp[] 数组里存储的就是相应元素地位之前的最大递增子序列长度，咱们只需遍历 dp[] 数组寻找出最大值，即可求得整个数组的最大递增子序列长度：
int res = 0; for(int k = 0; k < dp.length; k++){ res = Math.max(res, dp[k]); }此题代码也就写完了，上面贴出残缺代码:
class Solution { public int lengthOfLIS(int[] nums) { if(nums.length < 2) return 1; int[] dp = new int[nums.length]; Arrays.fill(dp,1); for(int i = 0;i < nums.length;i++){ for(int j = 0;j < i;j++){ if(nums[j] < nums[i]){ dp[i] = Math.max(dp[i],dp[j] + 1); } } } int res = 0; for(int k = 0;k < dp.length;k++){ res = Math.max(res,dp[k]); } return res; }}这个题两层 for 循环跟之前兑换零钱的代码基本上差不多，大家能够联合上一篇文章再一起比照了解。
不同之处只是内层 for 循环的判断条件和状态转移方程的表白（如何更新 dp[]），这也是动静布局的实质所在。
小结
对于动静布局有很多误区和误会，比方最常见的可能就是说它是空间换工夫，以及搞不清楚它和贪婪的区别。
心愿这两篇动静布局的文章能帮你打消这些误区，并且更好的了解到动静布局的实质，了解状态和状态方程。
当然，仅仅这两篇文章想说透动静布局是远远不够的，所以接下来会具体的解说一些典型问题，比方背包问题、石子游戏、股票问题等等，心愿能帮你在学习算法的路线上少走一些弯路。
如果大家有什么想理解的算法和题目类型，十分欢送在评论区留言通知我，咱们下期见！