Clear and easy method using DP in C++


  • 1
    L
    // The method, in DP idea, costs lots of time, but the logic is very eary and clear.
    //用时蛮长的,但思路比较清晰 
    // f[m][i] means if we could split the array [0, i] in m subarray, the minimal value of the largest sum among these m subarrays we could get.
    //f[m][i]表示m刀,在[0, i]的最小化subarray的最大值
    // Then, f[m][i] = min (maxf[m-1][j], sum(nums[from j + 1 to i])), where j = [0, i - 1];
    //递归式子:f[m][i] = min(max(f[m-1][j], sum(nums[j+1 - i])) 其中,j = [0, i - 1];
    // The complexity is O(n^3)
    //这样处理的话,就是三重循环了
    
    class Solution {
    public:
        int splitArray(vector<int>& nums, int m) {
            int len = nums.size();
            vector<vector<long>> arr(m, vector<long>(len, 0));
            arr[0][0] = nums[0];
            for(int i = 1; i<len; i++)
            {
                arr[0][i] = arr[0][i - 1] + nums[i];
            }
            
            for(int k = 1; k<m; k++)
            {
                for(int i = 0; i<len; i++)
                {
                    long minVal = arr[0][i];
                    for(int j = i-1; j>= 0; j--)
                    {
                        long tmpVal = max(arr[0][i] - arr[0][j], arr[k - 1][j]);
                        minVal = min(minVal, tmpVal);
                    }
                    arr[k][i] = minVal;
                }
            }
            return arr[m-1][len - 1];
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.