# Clear and easy method using DP in C++

• ``````// 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];
}
};

``````

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