Блог пользователя adaptatron

[Tutorial] : LIS using Trie : Longest Increasing Subsesquence
Автор adaptatron, 2 месяца назад, По-английски

The problem of computing the length of the Longest Increasing Subsesquence is usually solved via DP, Binary Search or Segment Tree. I created a blog discussing a Trie based approach that can solve this problem with very few lines of code.

https://cfstep.com/training/tutorials/dp/lis-using-trie/

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

So cool

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I would argue that the segment tree solution is at least as good as the trie solution and they are equivalent for some segment tree implementations, but that is an interesting way of viewing it.

→ Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    An "infinite binary trie stored in a sparse way" is exactly a sparse segment tree. Still, it is cool that you were able to 'reinvent' it through a slightly different way of thinking.

    → Ответить