[Question] - The combining of both forward and backward DP in a single loopproblem
Разница между en1 и en2, 11 символ(ов) изменены
Recently, I encounter this [problem:1741] that combine both forward and backward DP style, that make me feel surprised. I thought that we could only use either forward and backward DP in a problem to solve it. But in this problem we use both? Let call dp[i] is can we separate array from [1,i] into valid segments. Then:↵

The backward DP: if from range [1,i] we can not separate array into valid segments then we try to make the current number at index i as the length of the last segment => Check backward the range [1,i — b[i] — 1].↵

The forward DP: if we can separate array into valid segments in range [1,i-1], then the current number at index i can possibly length of the next segments => Update dp[i + b[i]] = true.↵

The doubt is can I combine both forward and backward DP style in all DP problems? If not, in what case/what type of DP properties the combination of forward and backward style will work? Do we have any related problems that require to combine both styles like this?↵

Thank in advance.↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский lvisbl_ 2024-06-20 20:35:12 1 Tiny change: 'oblem:1741] that com' -> 'oblem:1741E] that com'
en3 Английский lvisbl_ 2024-06-20 20:34:29 0 Tiny change: 'nter this [problem:1741] that comb' -> 'nter this that comb'
en2 Английский lvisbl_ 2024-06-20 20:33:41 11
en1 Английский lvisbl_ 2024-06-20 20:33:21 1106 Initial revision (published)