410. 分割数组的最大值

410. 分割数组的最大值

dp+前缀和

后悔啊。。。华师机试这一题没写出来
就这一个状态转移方程。。没想出来

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n=nums.size();
        long long f[n+1][m+1];
        memset(f,0x3f,sizeof f);
        vector<long long> s(n+1,0);
        for(int i=0;i<n;i++){
            s[i+1]=s[i]+nums[i];
        }
        f[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                for(int k=0;k<i;k++){
                    f[i][j]=min(f[i][j],max(f[k][j-1],s[i]-s[k]));
                }
            }
        }
        
        return f[n][m];
    }
};

二分

class Solution {
public:
    bool check(vector<int>&nums,int x,int m){
        int sum=0;
        int cnt=1;
        for(int i=0;i<nums.size();i++){
            if(sum+nums[i]>x){
                cnt++;
                sum=nums[i];
            }else{
                sum+=nums[i];
            }
        }
        return cnt<=m;
    }
    int splitArray(vector<int>& nums, int m) {
        int l=0,r=0;
        for(int i=0;i<nums.size();i++){
            r+=nums[i];
            l=max(l,nums[i]);
        }

        while(l<r){
            int mid=(l+r)>>1;
            if(check(nums,mid,m)){
                r=mid;
            }else l=mid+1;
        }
        return l;
    }
};