前言
在上一篇文章动态规划的文章中，我们先由Fibonacci 例子引入到了动态规划中，然后借助兑换零钱例子，分析了动态规划最主要的三个性质，即：
- 重叠子问题
- 最优子结构
- 状态转移方程
但是动态规划远不止这么简单
不入虎穴焉得虎子。今天这篇文章，让我们深入动态规划，一窥动态规划本质
我们既然要彻底搞清楚动态规划,那么一个不可避免的问题就是：
递归，贪心，记忆化搜索和动态规划之间到底有什么不同？
动态规划于递归 ：只是单纯的空间换时间吗？ No,斐波那切数列的例子很好的推翻了这个猜测
动态规划于贪心：只是贪心的加强版吗？No,零钱兑换例子同样推翻了这个猜想
那么，到底动态规划的核心是什么？要回答这个问题，我们不妨先引出下边这个问题
到底哪些问题适合用动态规划，即怎么鉴定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=newint[nums.length];
（注意这里dp数组的大小跟上一节兑换零钱例子有一丢丢不同，即这里没有+1，区别点大家可以返回上一节仔细理解一下）
那么这里dp数组的含义就是：
dp[i]保存的值即是给定数组i位之前最长递增子序列的长度
那么我们的初始状态是什么呢，我们知道状态的边界情况为：
F~1~ = 1
即如果数据只有一位那么应该返回1，（当数据个数>1个时）如果整个数列没有出现第二个递增的数，那么同样返回1
所以，初始状态我们给dp数组每个位置都赋为1
Arrays.fill(dp, 1);
1.我们从给定数组的第一个元素开始遍历，即写出外层的for循环：
for(inti=0; i<nums.length;i++){
......
}
2.当我们外层遍历到某元素时，我们怎么做呢？
我们得找一下，在这个(外层)元素之前，存不存在比它小的数，如果存在，那么我们就更新此外层元素的dp[i]
(如果某元素之前有比它小的数，那么这不就构成了递增子序列了吗，大家多理解几遍~)
因此我们可以写出内层for循环
for (intj=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[]数组寻找出最大值，即可求得整个数组的最大递增子序列长度：
intres=0;
for(intk=0; k<dp.length; k++){
res=Math.max(res, dp[k]);
}
此题代码也就写完了，下面贴出完整代码:
classSolution {
publicintlengthOfLIS(int[] nums) {
if(nums.length<2) return1;
int[] dp=newint[nums.length];
Arrays.fill(dp,1);
for(inti=0;i<nums.length;i++){
for(intj=0;j<i;j++){
if(nums[j] <nums[i]){
dp[i] =Math.max(dp[i],dp[j] +1);
}
}
}
intres=0;
for(intk=0;k<dp.length;k++){
res=Math.max(res,dp[k]);
}
returnres;
}
}
这个题两层for循环跟之前兑换零钱的代码基本上差不多，读者可以详细对比和理解一下
不同之处只是内层for循环的判断条件和状态转移方程的表达(如何更新dp[])
请读者们再细细的品一下~
好啦，今天的内容就先到这里啦~
欢迎各位小可奈们评论区交流留言~
