[LeetCode] 446. Arithmetic Slices II - Subsequence

01.07.2024

1. Problem

2. The Things I tried

I tried backtracking or a recursive function. But I could not make it and also the quiality of code was bad too.

3. Solution

3-1. Code

var numberOfArithmeticSlices = function(nums) {
    const n = nums.length;
    let total_count = 0;

    const dp = new Array(n).fill().map(() => new Map());

    for (let i = 1; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            const diff = nums[i] - nums[j];

            if (dp[j].has(diff)) {
                dp[i].set(diff, (dp[i].get(diff) || 0) + dp[j].get(diff));
                total_count += dp[j].get(diff);
            }

            dp[i].set(diff, (dp[i].get(diff) || 0) + 1);
        }
    }

    return total_count;
};

3-2. Explanation

3-3. Reference

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/solutions/4520265/98-43-easy-solution-with-dynamic-programming/

4. What I Learned

1. Shift()
2. Map functions