动态规划之最长递增子序列
基本归纳法：考虑Ai+1时, 仅需关注前一状态Ai即可完成整个推演过程. 它的一个显著特征是确定了Ai之后, 则计算Ai+1时无需关注A0到Ai-1之间的任何中间状态. 我们称这种模型为马尔可夫链.
在高阶归纳法中（或称作递归归纳法），对于后续的状态Ai+1来说（或称作第i+1个状态），需要考察前面的所有状态集{A_0, A_1, ..., A_i}才能完成整个系统的推理过程（或称作演算过程）。这通常被称为高阶马尔科夫模型（或称作马尔科夫过程的一种扩展）。
在计算机算法领域中，在进行高阶马尔科夫模型的相关推导时会采用动态规划这一方法；而当处理标准马尔科夫模型时，则采用贪心法这一策略。
LIS（Maximum Growth Subsequence），对于长度为N的数组A而言，旨在找出其中最长的非递减子序列（不一定是连续的）。
如：给定数组A{5,6,7,1,2,8}，则A的LIS为{5,6,7,8}；长度为4
方案一：通过LCS算法实现LIS求解。具体来说，在此方案下，我们需要将输入数组进行排序处理，并在处理后的结果中寻找与原始顺序匹配的部分。这一过程实际上等价于计算新旧两个有序序列之间的最长公共子序列长度。
方法二：动态规划：
思想：
| Array | 1 | 4 | 6 | 2 | 8 | 9 | 7 |
|---|---|---|---|---|---|---|---|
| LIS | 1 | 2 | 3 | 2 | 4 | 5 | ? |
长度为N的数组记为A{a0,a1.....an-1}；
称由前n个字符组成的前缀串为Ai = a0a1...ai-1；以ai结束的最长递增子序列为Li，并设其长度值为b[i]；
假设已经得到了b[0,1....i-1],如何计算得到bi？
如果将ai缀到L0 L1....LIi后面，是否允许呢？
可知若a_i > a_j成立则可将a_i连接到L_j之后的位置上从而形成一个比L_j长度更长的子序列并由此可得b_i=\max\{b_k \mid j < k \leq i \text{ 且 } a_k < a_i\} + 1
时间复杂度为O(N^2)；
代码实现：
int LIS(int *p,int length)
{
int longest[length];
int i,j;
for(i=0;i<length;i++)
{
longest[i] = 1;
}
int nLis = 1;
for(i=1;i<length;i++)
{
for(j=0;j<i;j++)
{
if(p[i]>p[j])
{
longest[i] = max(longest[i],longest[j]+1);
}
}
nLis = max(nLis,longest[i]);
}
delete []longest;
return nLis;
}如果是想要求出该最长子序列呢？很简单，记录前驱即可。
int LIS(int *p,int *pre;int length)
{
int longest[length];
int i,j;
int nIndex = 0;
for(i=0;i<length;i++)
{
longest[i] = 1;
pre[i] = -1;
}
int nLis = 1;
for(i=0;i<length;i++)
{
for(j=0;j<i;j++)
{
if(p[i]>p[j])
{
if(longest[i]<longest[j]+1)
{
longest[i] = longest[j]+1;
pre[i] = j;
}
}
}
if(nLis<longest[i])
{
nLis = longest[i];
nIndex = i;
}
}
delete []longest;
return nLis;
}