题目描述
有一个序列有N个数，A[1],A[2],A[3],……,A[N]，求出最长非降子序列长度。
我们首先我定义一个“状态”来代表它的子问题，并且找到它的解。一般情况下，某个状态只与它前面出现的状态有关，而独立于后面的状态。
假如我们考虑求A[1],A[2],A[3],………,A[i]的最长非降子序列的长度，其中i<N,那么这个问题就是原问题的一个子问题，然后我们定义d(i),表示前i个数中，以A[i]结尾的最长非降子序列的长度。只要我们把d(1)到d(N)都计算出来，那么答案就是这里面最大的那个。现在我们来求状态转移方程。
举一个例子，有如下序列
5,3,4,8,6,7
我们可以得到
- 前1个数的LIS长度d(1) = 1 （5）
- 前2个数的LIS长度d(2) = 1 （3）
- 前3个数的LIS长度d(3) = 2 （3,4 d(3) = d(2)+1）
- 前4个数的LIS长度d(4) = 3 ( 3,4,8 d(4) = max{d(1),d(2),d(3)}+1)
由上我们可以看出状态转移方程为d(i) = max{d[A[j]}+1 j<i && A[j]<=A[i]。
代码如下
vector<int> nums{5,3,4,8,6,7};
void LIS(vector<int>& nums) {
if (nums.empty()) return ;
vector<int> dp;
int len = nums.size();
for (int i = 0;i < len;i++) {
dp.push_back(1);
}
for (int i = 1;i<len;i++) {
for (int j=0;j<i;j++) {
if (nums[i]>=nums[j] && dp[j]+1>dp[i])
dp[i] = dp[j]+1;
}
}
ostream_iterator<int> oo(cout," ");
copy(dp.begin(),dp.end(),oo);
return ;
}
结果为
1 1 2 3 3 4
