Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×

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

How to calculate only the LCS's length of two strings with [2][max(n1,n2)] memory?
Автор MKGAURAB, 9 лет назад, По-английски

We generally use [n1][n2] memory to calculate the LCS length of two strings having length n1 and n2. Can it be calculated in [2][max(n1,n2)]? Can any one explain it clearly?

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

»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Not only it can be calculated using a matrix, it can also be calculated using a matrix (or even a vector). See here.

If you're looking for a "general" explanation of how you can use less memory in some DP tasks, then have a look at this.

→ Ответить