1.题目基本信息

1.1.题目描述

给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。

设计一个算法使得这 k 个子数组各自和的最大值最小。

1.2.题目地址

https://leetcode.cn/problems/split-array-largest-sum/description

2.解题方法

2.1.解题思路

贪心+动态规划

2.2.解题步骤

第一步，状态定义，dp[i][j]，指前i位分为j段的最大值中的最小，默认为无穷大

第二步，获取前n项和的数组，以方便获取第m到第j为的和

第三步，初始化第一位

第四步，动态转移;dp[i][j]=min(dp[i][j],max(dp[m][j-1],sub(m+1,i))) 【其中0<=m

3.解题代码

Python代码

class Solution:
    # 动态规划
    def splitArray(self, nums: List[int], k: int) -> int:
        length=len(nums)
        # 第一步，状态定义，dp[i][j]，指前i位分为j段的最大值中的最小，默认为无穷大
        dp=[[inf]*(k+1) for _ in range(length+1)]
        # 第二步，获取前n项和的数组，以方便获取第m到第j为的和
        subNums=[0]
        for i in range(length):
            subNums.append(subNums[-1]+nums[i])
        # 第三步，初始化
        dp[0][0]=0
        # 第四步，动态转移;dp[i][j]=min(dp[i][j],max(dp[m][j-1],sub(m+1,i))) 【其中0<=m<i】
        for i in range(1,length+1):
            for j in range(1,min(i,k)+1):
                for m in range(i):
                    dp[i][j]=min(dp[i][j],max(dp[m][j-1],subNums[i]-subNums[m]))
        # print(dp)
        # print(dp[length][k])
        return dp[length][k]

C++代码

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int length=nums.size();
        int dp[length+1][k+1];
        for(int i=0;i<length+1;++i){
            for(int j=0;j<k+1;++j){
                dp[i][j]=INT_MAX;
            }
        }
        vector<int> subNums;
        subNums.push_back(0);
        for(int i2=0;i2<length;++i2){
            subNums.push_back(subNums[subNums.size()-1]+nums[i2]);
        }
        dp[0][0]=0;
        for(int i3=1;i3<length+1;++i3){
            for(int j3=1;j3<min(i3,k)+1;++j3){
                for(int m=0;m<i3;++m){
                    dp[i3][j3]=min(dp[i3][j3],max(dp[m][j3-1],subNums[i3]-subNums[m]));
                }
            }
        }
        return dp[length][k];
    }
};

4.执行结果