[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?

#### History

Revisions

Rev. Lang. By When Δ Comment
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)