最长上升子序列(LIS)算法

理解:该子序列中后一项都比前一项大,例如有序列2 7 1 5 6 4 3 8 9,则最长上升子序列为2 5 6 8 9。 具体应用:用于确定一个代价最小的调整方案,使一个序列变为升序。只需要固定LIS中的元素,调整其他元素即可。 动态规划实现 O(n2)我们将序列存入数组a中,定义一个dp数组,存放最大长度。 2 7 1 5 6 4 3 8 9 我们能够得出一个规律: dp[i] = 前面v...
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×