410. 分割数组的最大值

第一次写题
二分法：

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        if(nums.size() == m) return *max_element(nums.begin(), nums.end());
        int iSum = 0;
        for(auto x: nums)
            iSum += x;
        int l = *max_element(nums.begin(), nums.end()), r = iSum;
        while(l < r)
        {
            int mid = ((long long)l + (long long)r) >> 1;
            int iPart = 0;
            int iPartCnt = 1;
            for(int i = 0; i < nums.size(); i++)
            {
                if(iPart + nums[i] <= mid)
                {
                    iPart += nums[i];
                }
                else
                {
                    iPart = nums[i];
                    iPartCnt++;
                }
            }
            // cout << l << ' ' << r << ' ' << mid << ' ' << iPartCnt << endl;
            if(iPartCnt <= m)//相当于说我每一个段都想让它小于等于mid（eg, iSum），它做到了，所以我的right可以减小
            {
                r = mid;
            }
            else{
                l = mid + 1;
            }
        }
        return r;
    }
};

dp:

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        vector<vector<long long>> aDp = vector<vector<long long>>(nums.size() + 1, vector<long long>(m + 1, INT_MAX));
        vector<long long> aSub(nums.size() + 1, 0);
        for(int i = 0; i < nums.size(); i++)
            aSub[i + 1] = aSub[i] + nums[i];
        aDp[0][0] = 0;
        for(int i = 1; i <= nums.size() ; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                for(int k = j - 1; k < i; k++)//nums的第几个数 
                {
                    aDp[i][j] = min(aDp[i][j], max(aDp[k][j - 1], aSub[i] - aSub[k]));//aDp[k][j - 1]前面 j - 1 part，j - 1 个数字
                }
            }
        }
        return aDp[nums.size()][m];
    }
};

dfs 超时：

class Solution {
    vector<long long> aPart;
    vector<int> aCnt;
    vector<int> nums;
    long long iRes = INT_MAX;

    void dfs(int idx, int ipart)
    {
        if(idx == nums.size())
        {
            if(*min_element(aCnt.begin(), aCnt.end()) == 0) return;
            // cout << aPart[0] << ' ' << aPart[1] << endl;
            iRes = min(iRes, *max_element(aPart.begin(), aPart.end()));
            return;
        }
        if(ipart >= aPart.size()) return;
            aPart[ipart] += nums[idx];
            aCnt[ipart] ++;
            dfs(idx + 1, ipart);
            dfs(idx + 1, ipart + 1);
            aPart[ipart] -= nums[idx];
            aCnt[ipart] --;
    }
public:
    int splitArray(vector<int>& _nums, int m) {
        nums = _nums;
        if(nums.size() == 0) return 0;
        long long sum = 0;
        for(int i = 0; i < nums.size(); i++)
            sum += nums[i];
        if(m == 1) return sum;
        aPart = vector<long long>(m, 0);
        aCnt = vector<int>(m, 0);
        dfs(0, 0);
        return iRes;

    }
};

第二次写题

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        if(m == nums.size()) return *max_element(nums.begin(),nums.end());
        // vector<vector<int>> aDp(nums.size() + 1, vector<int>(m + 1, INT_MIN));
        long long iSum = 0;
        for(auto x: nums) iSum += x;
        if(m == 1) return iSum;
        long long l = *max_element(nums.begin(), nums.end()), r = iSum;
        while(l < r)
        {
            long long mid = ((long long)l + (long long)r) >> 1;
            long long iPart = 0;
            int iCnt = 1;
            for(auto x: nums)
            {
                if(iPart + x <= mid)
                {
                    iPart += x;
                }
                else
                {
                    iPart = x;
                    iCnt++;
                }
            }
            if(iCnt <= m) r = mid;
            else l = mid + 1;
        }
        return r;

    }
};

dp：

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        vector<vector<long long>> aDp(nums.size() + 1, vector<long long>(m + 1, INT_MAX));
        aDp[0][0] = 0;
        vector<long long> aSub(nums.size() + 1);
        for(int i = 1; i <= nums.size(); i++)
        {
            aSub[i] = aSub[i - 1] + nums[i - 1];
        }
        for(int i = 1; i <= nums.size(); i++)
        {
            for(int j = 1; j <= m; j++)
            {
                for(int k = j - 1; k < i; k++)
                    aDp[i][j] = min(aDp[i][j], max(aDp[k][j - 1], aSub[i] - aSub[k]));
            }
        }
        return aDp[nums.size()][m];
    }
};

dfs

class Solution {
    vector<long long> aPartSum;
    vector<int> aPartCnt;
    long long iRes = INT_MAX;
    int m;
    vector<int> nums;
    void dfs(int idx, int part)
    {
        if(part >= m) return;
        if(idx == nums.size())
        {
            if(*min_element(aPartCnt.begin(), aPartCnt.end()) == 0)
                return;
            else
            {
                iRes = min(iRes, *max_element(aPartSum.begin(), aPartSum.end()));
                return;
            }
        }
        aPartSum[part] += nums[idx];
        aPartCnt[part] += 1;
        dfs(idx + 1, part);
        dfs(idx + 1, part + 1);
        aPartSum[part] -= nums[idx];
        aPartCnt[part] -= 1;

    }
public:
    int splitArray(vector<int>& _nums, int _m) {
        m = _m;
        nums = _nums;
        aPartSum = vector<long long>(m, 0);
        aPartCnt = vector<int>(m, 0);

        dfs(0, 0);
        return iRes;
    }
};