<p>Given an integer array <code>nums</code> and an integer <code>k</code>, split <code>nums</code> into <code>k</code> non-empty subarrays such that the largest sum of any subarray is <strong>minimized</strong>.</p>

<p>Return <em>the minimized largest sum of the split</em>.</p>

<p>A <strong>subarray</strong> is a contiguous part of the array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [7,2,5,10,8], k = 2
<strong>Output:</strong> 18
<strong>Explanation:</strong> There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5], k = 2
<strong>Output:</strong> 9
<strong>Explanation:</strong> There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= k &lt;= min(50, nums.length)</code></li>
</ul>

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        """
        dp[i][j] represents minimal max group sum of nums[:i+1] with j + 1 groups
        dp[i][j] = min(
            max(dp[i - 1][j - 1], nums[i]),
            max(dp[i - 2][j - 1], nums[i] + nums[i - 1]),
            max(dp[i - 3][j - 1], nums[i] + nums[i - 1] + num[i - 2])
        )
        j <= i
        dp[0][0]: [nums[0]], 1 group
        dp[1][0]: [nums[0], nums[1]], 1 group
        dp[1][1]: [nums[0], nums[1]], 2 group
        """
        dp = [[float('inf') for j in range(k)] for i in range(len(nums))]
        dp[0][0] = nums[0]
        for i in range(1, len(nums)):
            # print('!', i, min(i + 1, k))
            dp[i][0] = dp[i - 1][0] + nums[i]
            for j in range(1, min(i + 1, k)):
                # print(i, j)
                dp[i][j] = max(dp[i - 1][j - 1], nums[i])
                p = i - 1
                cur_sum = nums[i]
                while p > 0 and p > j - 1:
                    cur_sum += nums[p]
                    p -= 1
                    dp[i][j] = min(dp[i][j], max(dp[p][j - 1], cur_sum))
        # for row in dp:
        #     print(row)
        return dp[-1][-1]


18300