LC 100136. 统计好分割方案的数目

https://leetcode.cn/problems/count-the-number-of-good-partitions/description/

如果是用前向搜索的话，好像枚举状态会比较多，所以比较适合从后往前搜索。

我这里写个一个DP状态方程，看的出来似乎是需要保持另外一个数组来进行累计。

\(dp[i] = dp[j+1] + .. + dp[n-1]. st. nums[i] = nums[j]\)
\(acc[i] = acc[i] + acc[i+1] + ... + acc[n-1]\)

对于第一个条件，还有一个附加条件，就是这个 i 必须是最开始的下标，比如 `[1,5,1,5,8]` 为例：

对于 i=0 来说，它的last其实是 i=3 这个下标
但是对于 i=1 来说，其实它并不是有效的前缀，所以这里 `last[i]=-1`.
这个在状态转移的时候需要稍微判断一下。

如果我们要求解到有效的 `last` 的话，需要多轮枚举。还是以 `[1,5,1,5,8]` 为例：

i=0, 它的直接last是 i=2
但是中间i=1包含了5, 而它的last是i=3
所以i=0的last应该是i=3.

class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int:
        # dp[i] = dp[j+1] + .. + dp[n-1]  where nums[i] = nums[j].
        # acc[i] = acc[i] + acc[i+1] + ... + acc[n-1]
        n = len(nums)

        direct = {}
        for i in range(n):
            direct[nums[i]] = i

        last = [-1] * n
        visited = [0] * n
        for i in range(n):
            if visited[i]: continue
            j = i
            end = direct[nums[i]]
            while j < end:
                end = max(direct[nums[j]], end)
                j += 1
            last[i] = end
            for k in range(i, j + 1):
                visited[k] = 1

        MOD = 10 ** 9 + 7
        # print(last)
        dp = [0] * n
        acc = [0] * (n + 1)
        acc[-1] = 1
        for i in reversed(range(n)):
            p = last[i]
            if p == -1:
                dp[i] = 0
            else:
                dp[i] = acc[p + 1]
            acc[i] = (acc[i + 1] + dp[i]) % MOD
        return dp[0]