<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:
        """
        Solution: https://www.youtube.com/watch?v=YUF3_eBdzsk&list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO&index=45
        - First Solution
        - DP
        - Subproblem: min max sum of nums[i:] with k splits for all i in (0..n-k) for k in (1..m)
        - Relation: For a first split at i, with m total splits, the min max sum is the min betweenn sum(numx[:i]) and the min max sum at i+1 with m-1 split
        - limit case: if m==1, the solution is the sum of the current considered list
        """
        n =  len(nums)
        dp = {}
        def dfs(i:int, m:int)->int:
            """
            Min Max Subsarray Sum for the array starting at i, with m possible splits
            """
            if m==1:
                return sum(nums[i:])
            if (i,m) in dp:
                return dp[(i,m)]
            
            curSum, res = 0, float("inf")
            for j in range(i,n-m+1):
                curSum += nums[j]
                if curSum > res:
                    break
                # Get Max SubstringSum with a first split at i
                maxSum = max(curSum, dfs(j+1,m-1))
                # Keep the optimal solution
                res = min(res,maxSum)
            dp[(i,m)] = res
            return res
        return dfs(0,k)
        
        
22200