DP solution easy to understand


  • 1
    A

    We create two arrays: local and global. local[i] means solutions that must contains A[i], and global[i] means all solutions between 0 ~ i. so we have formula:
    local[i] = local[i - 1] + 1 if (A[i] - A[i - 1] == A[i - 1] == A[i - 2]) otherwise local[i] = 0;
    global[i] = global[i - 1] + local[i]
    Here is my code:

    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            int len = A.length;
            if (len <= 2) return 0;
            int[] local = new int[len];
            for (int j = 2; j < len; j++) {
                if (A[j] - A[j - 1] == A[j - 1] - A[j - 2]) local[j] = local[j - 1] + 1;
                else local[j] = 0;
            }
            int[] dp = new int[len];
            for (int i = 2; i < len; i++) {
                dp[i] = dp[i - 1] + local[i];
            }
            return dp[len - 1];
        }
    }
    

Log in to reply
 

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