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.↵
↵
↵
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.↵
↵
