有一个长为n的数列a0,a1,---,an-1.求出这个序列中最长的上升子序列的长度,限制条件是1<=n<=1000,0<=ai<=1000000;
int dp[1000];
int number[1000];
第一种dp是将dp[i]看做到i为止的最长子序列的个数,递推关系是从前i-1个dp元素中选出number[x]小于a[i],即可将a[i]加入最长子序列中所以dp[x]+=1,dp[i]的值就是遍历a[0]到a[i]得到最大dp[x]
递推公式dp[i]=max(1,dp[j]+1),j<i
int i = 0;
int res = 0;
cin >> i;
for (int j = 0; j < i; j++)
{
dp[j] = 1;
cin >> number[j];
for (int k = 0; k < j; k++)
{
if (number[j] > number[k])
{
res = max(dp[j], dp[k]+1);
}
dp[j] = max(res, dp[j]);
}
}
cout << "最大为"<<dp[i-1];
cin >> i;
第二种方把dp数组代表最长子序列本身,dp[i]为到i为止的最长子序列中最大值(最小的最大值,有比他小的即更新,但比前面i-1个要小),这样能通过下标来判断个数
int res = 0;
int middleMax( int a)
{
if (dp[res] < a) {
res++;
return res;
}
int first = 0;
int last = res;
while (last!=first)
{
int middle = (first + last) / 2;
if (dp[middle] < a)
{
first = middle;
}
else if (dp[middle] == a)
{
return middle;
}
else
{
last = middle;
}
}
for (int q = 0; q < i; q++)
{
dp[q] = maxNumber;
cin >> number[q];
dp[middleMax( number[q])] = number[q];
}
int s = 0;
for (int k = 0; k < i; k++)
{
if (dp[k] < maxNumber)
s++;
else
break;
}
cout << s;
个人目前理解DP是记录各个子问题的解,通过各个子问题的解求出问题的解,如子序列的最长个数是序列的最长个数的子问题,整个序列的最长个数通过遍历所有的子问题得出最大值。DP[i]表示什么也很重要,第二种DP[i]跟第一种表示不同,但是时间复杂度更少,是O(n*logn)再就是递归方程式,写出来才能做下去,个人愚见,权当学习记录
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。