2464. Minimum Subarrays in a Valid Split

You are given an integer array nums.

Splitting of an integer array nums into subarrays is valid if:

• the greatest common divisor of the first and last elements of each subarray is greater than 1, and
• each element of nums belongs to exactly one subarray.

Return the minimum number of subarrays in a valid subarray splitting of nums. If a valid subarray splitting is not possible, return -1.

Note that:

• The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.
• A subarray is a contiguous non-empty part of an array.

long long dp[1010];
class Solution {
    long long helper(vector<int>& A, int pos) {
        if(pos == A.size()) return 0;
        if(dp[pos] != -1) return dp[pos];
        long long& res = dp[pos] = INT_MAX;
        for(int i = pos; i < A.size(); i++) {
            int g = __gcd(A[i],A[pos]);
            if(g == 1) continue;
            res = min(res, 1 + helper(A,i+1));
        }
        return res;
    }
public:
    int validSubarraySplit(vector<int>& nums) {
        memset(dp,-1,sizeof dp);
        long long res = helper(nums, 0);
        return res > nums.size() ? -1 : res;
    }
};