Please read the new rule regarding the restriction on the use of AI tools. ×

Need explanation for this Atcoder #230 F Problem DP problem.

Revision en1, by THE_BOMBE, 2021-12-27 13:18:03

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 f 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)