C++ DP Solution


  • 0
    0

    dp[i] is the number of arithmetic slices which end with A[i].
    sum of all dp[i] (0 <= i < A.size) is the result.

    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            int len = A.size();
            if(len < 3)
                return 0;
            vector<int> dp(len, 0);
            int res = 0;
            for(int i = 2; i < len; i++){
                dp[i] = (A[i] - A[i-1] == A[i-1] - A[i-2]) ? (dp[i-1] + 1) : 0;
                res += dp[i];
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.