# 2464. Minimum Subarrays in a Valid Split
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Math`
Link: https://leetcode.com/problems/minimum-subarrays-in-a-valid-split/description/
## 思路
基本型II

## Code

class Solution {
    public int validSubarraySplit(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE/2);
        for(int i=0; i<n; i++){
            for(int j=0; j<=i; j++){
                if(gcd(nums[j], nums[i])>1){
                    dp[i] = Math.min(dp[i], (j==0?0:dp[j-1])+1);
                }
            }
        }
        return dp[n-1]==Integer.MAX_VALUE/2?-1:dp[n-1];
    }
    public int gcd(int a, int b){
        if(b==0) return a;
        return gcd(b, a%b);
    }
}