动态规划 - 最长递增子序列LIS

问题：一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度

样例输入：3 1 2 6 5 4

思路：首先把问题简单化。可以先求A[1],...A[i]的最长非降子序列，令dp[i]为以A[i]结尾的最长非降子序列。当i= 1时，明显是长度dp[1]= 1； i = 2时，前面没有比1小的数字，故dp[2]=1，此时的最长非降子序列为1; i = 3时,比数字2小的数是1，并且只有1，分析可知dp[3] = dp[2]+1；当i= 4时，找到比数字6小的数有 3 1 2，求最长子序列，就应该找到前面的最长子序列的最大值max{ dp[1],dp[2],dp[3]},此时dp[4]=max{dp[j]+1},(j<4 , A[j]<A[4]) ;通过分析，我们可以归纳出状态转移方程为dp[i] = max{dp[j]+1 , 1}(j<i , A[j]<A[i]) ;

下面是代码：

/*最长非降子序列8月26日10:19:00动态规划*/#include<iostream>using namespace std ;int LIS (int A[] , int n );int main (){int A[] = {3,1,2,6,4,5} ;cout << LIS (A,6);return 0;}int LIS (int A[] , int n ){int *dp = new int[n] ;dp[0] = 0 ;int len = 1;int i , j ;for ( i=1 ; i < n ; i ++ ){dp[i] = 1 ;for ( j = 0 ; j <i ; j ++){if (A[j]<A[i]&&dp[j]+1>dp[i])dp[i] = dp[j]+1 ;if ( len < dp[i] )len = dp [i] ;}}delete []dp ;return len ;}

仅作个人理解，希望对没有基础的人有帮助