Need explanation for Atcoder ABC#230 F DP Problem.

Revision en3, by THE_BOMBE, 2021-12-27 13:20:49

https://atcoder.jp/contests/abc230/tasks/abc230_f

The above url is the link to the problem , i read many blogs but I am confused about why the recursive relation is given by

DP[i]=2*DP[i-1] - DP[j]
where j is the right most index such that sum of subarray from A[j+1] to A[i-1] is zero.

BUT why it is  not 

DP[i]=2*DP[i-1]- SUM(DP[j]) for all j such that sum of subarray from A[j+1] to A[i-1] is zero.

Please also point out some similar questions if you have, Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English THE_BOMBE 2021-12-27 13:20:49 1 Tiny change: ' that sum f subarray' -> ' that sum of subarray'
en2 English THE_BOMBE 2021-12-27 13:19:33 18
en1 English THE_BOMBE 2021-12-27 13:18:03 572 Initial revision (published)