Problem statement

https://binarysearch.com/problems/Recursive-Voting/

Solution

We can use dp here: dp(i) is answer for i-th element.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        @lru_cache(None)
        def dp(i):
            if i < 0: return 1
            if i >= len(A): return 0
            return dp(A[i])
        return sum(dp(i) for i in range(len(A)))