一点算法 | 动态规划
动态规划
数组最大不连续递增子序列
你看每一期算法都可能被用到，小编的朋友看完冒泡排序，才发现自己面试时讲错了，顿时感觉自己的面试凉凉，关注我偶尔为你复习一下！
进入正题开始学习
马尔科夫模型介绍
首先设置一个规模为n问题a，求解一个未知解为b。
我们将这个大问题a分成a0…an，先求解a0，之后根据a0得到a1，a0->a1，然后a1->a2，a2->a3….对于ai，我们只需要它的上一个状态a（i-1）即可解决，这样的模型称为马尔科夫模型。
动态规划概述
动态规划所解决的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。
这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。
一般有以下几个步骤：
1、划分阶段；
2、确定状态和状态变量；
3、确定决策并写出状态转移方程；
4、寻找边界条件。
求解动态规划，首先要明确问题要不要分阶段，每个阶段是什么状态，从前一阶段到后一阶段之间的递推关系，也就是状态转换方程是什么。一般得到状态转换方程基本上问题就已经解决一大半了。
动态规划的整个的求解过程可以用一个最优决策表来描述，看到这里，您是否想到之前学习的决策树？最优决策表的行表示阶段，列表示问题状态，表格需要填写的数据就是问题在某个阶段某个状态的最优值（迪杰斯特拉最短路径，这个之后再聊，很好玩。）
题目
求一组数组中的最长递增子序列的长度？
arr[] = {3,1,4,1,5,9,2,6,5}的最长递增子序列长度为4。即为：1,4,5,9
首先设置一个数组temp，长度为数组arr长度，每个基础值为1，代表目前包括i位置在内的和之前数据的最长递增子序列长度。（例i=2时，arr[2]=4，其temp[2]为2。对应数据为3，4。）
从i等于0开始往后推，每到一个数字（4的下一位是1）与它之前所有元素相比，如果有元素比这个数字小并且那个元素的temp值+1比这个数字的temp大，那么就将这个数字的temp设置为那个元素的temp值+1，一直比较到这个数字的时候即可确定这个数字的最终temp。
它的状态转换方程为temp[i]=max{temp[i-1], temp[i-1]+1}我们来列个表格详细介绍一下过程。
表格介绍
|
arr 数组 |
3 |
1 |
4 |
1 |
5 |
9 |
2 |
6 |
5 |
|
初始 temp |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
1 1 |
2 |
|
2 |
2 |
2 |
2 |
2 |
|
|
|
1 1 |
|
|
3 |
3 |
3 |
3 |
|
| 1 1 |
4 |
4 |
我们开始解释上面这个表格，首先元素3，因为他之前没有元素了，所以确定temp为1；然后是元素1，它之前是元素3，1比3小，所以元素1的temp不变。
然后是元素4，它之前有两个元素，从最左面元素3开始，元素3小于元素4且元素3的temp+1为2大于元素4的temp值1，所以设置4的temp值为元素3的temp+1即为2。
而对于元素3之后的1因为比4小所以不操作，则元素4的temp确定为2。再看往后两位的5，他前面有四个元素，从元素3开始比较，元素3小于元素5且元素3的temp+1等于2大于元素5的temp，则元素5的temp为2，再看元素3后的元素1。
虽然1小于5但是他的temp+1正好等于元素5的temp值，所以这里元素5的temp值不变，元素1后面是元素4，4小于5且元素4的temp+1大于5的temp，故而元素5的temp值更新为3。以此类推。
部分代码（java）：
public static int MaxChildArrayOrder(int a[]) {
int n = a.length;
int temp[] = new int[n];//temp[i]代表0...i上最长递增子序列
for(int i=0;i<n;i++){
temp[i] = 1;//初始值都为1
}
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(a[i]>a[j]&&temp[j]+1>temp[i]){
//如果arr[i]前面有元素比他小并且那个元素的temp+1比arr[i]的temp大，那么就把那个元素的temp+1的值赋值给arr[i]的temp。
temp[i] = temp[j]+1;
}
}
}
int max = temp[0];
//从temp数组里取出最大的值
for(int i=1;i<n;i++){
if(temp[i]>max){
max = temp[i];
}
}
return max;
}
总结
其实这段代码一开始我感觉时间复杂度有点高，因为i要跟i之前所有元素进行大小比较和temp值对比，想找一个数组保存最大temp值，这样就不用再从前往后一个一个的比较了。
看完在看一下