Question about memory reduction in Dynamic Programming

Правка en1, от Bekh, 2019-09-24 20:41:14

Hello,

I was trying to solve 383E - Гласные. Using the technique described here: https://codeforces.com/blog/entry/45223

I managed to get AC here: 61233188 using regular memory reduction (Reducing one of the dimensions to the size of 2).
I don't understand how it can be reduced to one-dimensional like this: 61233599.

Here is an image to demonstrate my understanding of the dp dependencies in this problem:

Теги #dp, #dynamic programing, memory reduction

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Bekh 2019-09-24 20:52:21 289 Tiny change: 'roblem:![ ](https://' -> 'roblem:![ ss](https://' (published)
en1 Английский Bekh 2019-09-24 20:41:14 536 Initial revision (saved to drafts)