Leetcode 2464. 有效分割中的最少子数组数目

geek0070 / 2024-09-22 / 原文

1.题目基本信息

1.1.题目描述

给定一个整数数组 nums。

如果要将整数数组 nums 拆分为子数组后是有效的，则必须满足:

每个子数组的第一个和最后一个元素的最大公约数大于 1，且
nums 的每个元素只属于一个子数组。
返回 nums 的有效子数组拆分中的最少子数组数目。如果不能进行有效的子数组拆分，则返回 -1。

注意:

两个数的最大公约数是能整除两个数的最大正整数。
子数组是数组中连续的非空部分。

1.2.题目地址

https://leetcode.cn/problems/minimum-subarrays-in-a-valid-split/description/

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

第一步，状态定义；dp[i]指nums中前i个元素的最小合法子数组数

第二步，状态初始化，前0个的最小组成数为0

第三步，状态转移；dp[i]=min(dp[i],dp[j-1]+1) (其中1<=j<=i并且nums[i-1]与nums[j-1]的最大公约数大于1)，状态数组的最后一个值为inf，则返回-1，否则dp[-1]即为最终题解

3.解题代码

Python代码

class Solution:
    def validSubarraySplit(self, nums: List[int]) -> int:
        length=len(nums)
        # 第一步，状态定义;dp[i]指nums中前i个元素的最小合法子数组数
        dp=[inf]*(length+1)
        # 第二步，状态初始化,前0个的最小组成数为0
        dp[0]=0
        # 第三步，状态转移;dp[i]=min(dp[i],dp[j-1]+1) (其中1<=j<=i并且nums[i-1]与nums[j-1]的最大公约数大于1)
        for i in range(1,length+1):
            for j in range(1,i+1):
                if gcd(nums[i-1],nums[j-1])>1:
                    dp[i]=min(dp[i],dp[j-1]+1)
        # print(dp)
        return dp[-1] if dp[-1]!=inf else -1