446. Arithmetic Slices II - Explanation

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0

        INF = float('inf')
        dp = {}

        def dfs(i, j, diff, flag):
            if i == n:
                return flag
            if (i, j, diff, flag) in dp:
                return dp[(i, j, diff, flag)]

            res = dfs(i + 1, j, diff, flag)
            if j == -1:
                res += dfs(i + 1, i, INF, flag)
            else:
                if diff == INF:
                    res += dfs(i + 1, i, nums[i] - nums[j], flag)
                elif diff == nums[i] - nums[j]:
                    res += dfs(i + 1, i, diff, 1)

            dp[(i, j, diff, flag)] = res
            return res

        return dfs(0, -1, INF, 0)

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        res, n = 0, len(nums)
        dp = [defaultdict(int) for _ in range(n)]

        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                dp[i][diff] += 1 + dp[j][diff]
                res += dp[j][diff]

        return res

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        res, n = 0, len(nums)
        s = set(nums)
        dp = [defaultdict(int) for _ in range(n)]

        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                cnt = dp[j].get(diff, 0)
                if nums[i] + diff in s:
                    dp[i][diff] += cnt + 1
                res += cnt

        return res

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        res = 0
        mpIdx = defaultdict(list)
        n = len(nums)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            mpIdx[nums[i]].append(i)

        for i in range(n):
            for j in range(i):
                prev = 2 * nums[j] - nums[i]
                if prev in mpIdx:
                    for k in mpIdx[prev]:
                        if k >= j:
                            break
                        dp[i][j] += dp[j][k] + 1
                res += dp[i][j]

        return res