Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

[Question] — The combining of both forward and backward DP in a single loop

Revision en1, by lvisbl_, 2024-06-20 20:33:21

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.

Tags dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English lvisbl_ 2024-06-20 20:35:12 1 Tiny change: 'oblem:1741] that com' -> 'oblem:1741E] that com'
en3 English lvisbl_ 2024-06-20 20:34:29 0 Tiny change: 'nter this [problem:1741] that comb' -> 'nter this that comb'
en2 English lvisbl_ 2024-06-20 20:33:41 11
en1 English lvisbl_ 2024-06-20 20:33:21 1106 Initial revision (published)