此题可以被看作是动态规划中的经典面试题,能用动态规划求解的问题的一般要具有以下3个性质:
1)最优化原理:如果问题的最优解所包含的子问题的解也是最优的,那么就称该问题具有最优子结构,即满足最优化原理。
2)无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
3)有重叠予问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)
下面我们看下动态规划求解的基本步骤。动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。动态规划的设计都有着一定的模式,一般要经历以下几个步骤:
初始状态→|决策1|→|决策2|→…→|决策n|→结束状态
1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。
2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。
一般只要解决问题的阶段、状态和状态转移决策确定了,就可以写出状态转移方程(包括边界条件)。
使用动态规划求解问题,最重要的就是确定动态规划三要素:
1)问题的阶段
2)每个阶段的状态
3)从前一个阶段转化到后一个阶段之间的递推关系。
下面我们来运用上面的理论来求解此题,根据上诉介绍我们首先要定义一个“状态”来代表它的子问题,并且找到它的解。注意,大部分情况下,某个状态只与它前面出现的状态有关,而独立于后面的状态。
对于本题而言,假设数组A长度为N,首先考虑求A[1],A[2],…,A[i]的最长非降子序列的长度,其中i<N,那么上面的问题变成了原问题的一个子问题(问题规模变小了,可以让i=1,2,3等来分析),然后我们定义d(i),表示前i个数中以A[i]结尾的最长非降子序列的长度。这个d(i)就是要找的状态。如果把d(l)到d(N)都计算出来,那么最终要找的答案就是这里面最大值。状态找到了,下一步需要找出状态转移方程。假设要求的这N个数的序列是:{2,3,4,5,2,3,4,9},这个序列正好是题目中数组的倒序。
根据上面找到的我们找到的状态方程,我们可以得到:(下文的最长非降子序列都用LIS表示)。
前1个数的LIS长度d(1)=1(序列:2);
前2个数的LIS长度d(2)=2(序列:2,3;3前面比它小的有1个数,所以d(2)=d(2)=d(1)+1);
前3个数的LIS长度d(3)=3(序列:2,3,4;4前面比它小的有2个数,所以d(3)=d(2)+1);
前4个数的LIS长度d(4)=4(序列:2,3,4,5,;5前面比它小的有3个数,所以d(4)=d(3)+1);
前5个数的LIS长度d(5)=1(序列:2,3,4,5;2前面没有比2小的数,所以d(5)=1。
最终dn的集合为{1,2,3,4,1,2,3,5}
分析到这里,状态转移方程已经很明显了,如果已经求出了d(1)到d(i-1),那么d(i)可以用下面的状态转移方程得到:
d(i)=max{1,d(j)+1},其中j<i,A[j]<=A[i]
通俗地讲就是,想要求d(i),就把i前面的各个子序列中,最后—个数不大于A[i]的序列长度加1,然后取出最大的长度即为d(i)。当然了,有可能i前面的各个子序列中最后一个数都大于A[i],那么d(i)=1,即它自身成为一个长度为1的子序列。
对于{9,4,3,2,5,4,3,2},可以看作是从a[n]到a[0]求连续递增的子串,求得最大子序列个数为5,表为dp={5,3,2,1,4,3,2,1}。那么db中以此找出{5,4,3,2,1}对应的原数组的值即为最大递减子序列。对应的为{9,5,4,3,2}。
根据上面的讲解,实现代码如下:
class Test
{
static void LIS(int[] arrar)
{
var length=arrar.Length;
//初始化DP数组长度
int[] dp=new int[length];
//连续予串长度
int maxlength=0;
for (int i=length-1;i>=0;i--)
{
int max=0;
dp[i]=1;
for(int j=i+1;j<length;j++)
{
if(arrar[j]<arrar[i]&&max<dp[j])
{
max=dp[j];
}
}
dp[i]=max+1;
maxlength=maxlength<dp[i]? dp[i]: maxlength;
}
for(int i=0;i<length; i++)
{
if(dp[i]==maxlength)
{
Console.Write(arrar[i]+" ");
maxlength--;
}
}
}
public static void Main(string[] args)
{
LIS(new int[]{9,4,3,2,5,4,3,2});
Console.Read();
}
}
程序的运行结果为:
9 5 4 3 2
算法性能分析:
以上这种方法需要进行双重循环,因此,时间复杂度为O(n2),其中,N为数组的长度。同时需要额外的空间来记录分组数据,因此,空间复杂度为O(n)。
[考点] 如何求一个数组的最长递减子序列