算法基础：使用动态规划法解决最长上升子序列问题

这篇文章继续介绍使用动态规划法解决LIS问题的方法。

LIS：最长上升子序列

LIS（最长上升子序列）: Longest Increasing Subsequence的缩写，指的是一个序列中最长的单调递增的子序列。

• 题目内容说明：求长度为n数列中的最长的上升子序列的长度。

定义DP数组

鉴于上述说明过于简略，这里借一张图来说明问题以及解决的思路 最简单的方式是使用同等长度的dp数组来解决问题，dp数组的具体含义如下：

dp[i]: 待求解数列中以第i个元素为结尾的最长上升子序列的长度。

求解方法

求解方法：如果第i-j个数字都比第i个大，dp[i]为1，如果比之前有比其大的，就在此基础上寻取最大解，所以就是一个两重循环进行问题的解决，所以没有优化的情况下，复杂度为n平方。

代码模拟

#include  #include  int max(int x, int y) { return x > y ? x : y; } int get_lis(int* arr, int num) { int* dp = malloc(sizeof(int) * num); int max_len = dp[0]; for (int i=0; i<num; i++) { dp[i]=1; for (int j=0; j<i; j++) { if (arr[i] > arr[j]) dp[i] = max(dp[i],dp[j]+1); } } for(int i=0; i<num; i++) max_len = max(max_len,dp[i]); free(dp); dp=NULL; return max_len; } int main(){ int n = 0; while(scanf("%d",&n) != EOF) { int* array = (int *)malloc(sizeof(int) * n); for (int i=0; i<n; i++) scanf("%d",&array[i]); printf("%d\n",get_lis(array,n)); free(array); array = NULL; } return 0; } 

示例执行结果如下：

8
10 9 2 5 3 7 21 18
4

总结

使用动态规划数组即可解决LIS的方式，但是n平方的复杂度实际上结合二分查找可以降到nlogn的程度，然后是否滚动数组是否可以使用，以及很多组合的方式都可能会出现，都是值得进一步思考的。