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

Правка en2, от lvisbl_, 2024-06-20 20:33:41

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.

Теги dynamic programming

История

 
 
 
 
Правки
 
 
  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)