---
# System prepended metadata

title: 2464. Minimum Subarrays in a Valid Split
tags: [Leetcode, Dynamic Programming, Medium, Math]

---

# 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
```dp[i]```表示```nums[0:i]```的minimum subarrays number
```dp[i] = min(dp[j-1]+1)``` ```j```是所有能使得```nums[j:i]```是一个valid split的index
## Code
```java=
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);
    }
}
```