i*********7
发帖数: 348 | 1 我现在看了好几个LIS的问题的解法。基本都是DP加二分，大都只能返回长度值。能不
能返回一个字符串，里面装的就是一个最长递增子序列。
譬如a = {1,5,3,6,8,2,10};
返回1,5,6,8,10或者1,3,6,8,10都可以。 | H****s
发帖数: 247 | 2 当然可以了，你自己写个函数根据记录的index恢复。 | w****x
发帖数: 2483 | 3 从后往前推 输出满足 a[i-1] <= a[i] && dp[i-1] == dp[i] - 1的元素,
几乎所有要输出元素而不是个数的DP题都是这么做的 | w***y
发帖数: 6251 | 4 我还不知道解法, 能不能给个link //bow | p*****2
发帖数: 21240 | 5
譬如a = {1,5,3,6,8,2,10};
返回1,5,6,8,10或者1,3,6,8,10都可以。
我也没做过这题。看了一下。可以纪录在每个点，前边比它小的元素个数。不知道有没
有更好的。
【在 w***y 的大作中提到】
: 我还不知道解法, 能不能给个link //bow
| X*K
发帖数: 87 | | w****x
发帖数: 2483 | 7
那个是O(n^2)的解法.
有个nlogn的解法, 用二分的, 很巧妙, 当年看了2小时才看明白, 而且怎么也记不住.
【在 p*****2 的大作中提到】
:
: 譬如a = {1,5,3,6,8,2,10};
: 返回1,5,6,8,10或者1,3,6,8,10都可以。
: 我也没做过这题。看了一下。可以纪录在每个点，前边比它小的元素个数。不知道有没
: 有更好的。
| p*****2
发帖数: 21240 | 8
哎。真不容易呀。
【在 w****x 的大作中提到】
:
: 那个是O(n^2)的解法.
: 有个nlogn的解法, 用二分的, 很巧妙, 当年看了2小时才看明白, 而且怎么也记不住.
| i**********e
发帖数: 1145 | 9 steven skienna 那本算法红宝书 DP 章节有介绍这道题，强烈推荐，解释的非常好。 | c*********t
发帖数: 2921 | 10 可是他讲的是O(n^2)
【在 i**********e 的大作中提到】
: steven skienna 那本算法红宝书 DP 章节有介绍这道题，强烈推荐，解释的非常好。
| | | i**********e
发帖数: 1145 | 11 是，后面的题后练习。
但是前面解释得很好，引导你可以用 binary search 优化的思路. | i**********e
发帖数: 1145 | | i*********7
发帖数: 348 | 13 输出还有nlogn的做法？
能求连接或者代码吗？
【在 w****x 的大作中提到】
:
: 那个是O(n^2)的解法.
: 有个nlogn的解法, 用二分的, 很巧妙, 当年看了2小时才看明白, 而且怎么也记不住.
| w****x
发帖数: 2483 | 14
没必要看nlogn的解法, 没必要
【在 i*********7 的大作中提到】
: 输出还有nlogn的做法？
: 能求连接或者代码吗？
| i******r
发帖数: 793 | 15 为啥没必要。。。
【在 w****x 的大作中提到】
:
: 没必要看nlogn的解法, 没必要
| i*********7
发帖数: 348 | 16 咳咳。我懂了。。因为光O(n^2)的算法，如果你基础不好，就要理解好一段时间。。。
【在 i******r 的大作中提到】
: 为啥没必要。。。
|
|
