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 的大作中提到】 : 为啥没必要。。。
|
|