<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 helper(self, dp, table, nums, idx, k):
        if (idx, k) in dp:
            return dp[(idx, k)]
        if k > len(nums) - idx:
            return math.inf
        if k == 1:
            dp[(idx, k)] = table[-1] - table[idx]
            return dp[(idx, k)]
        res, base = math.inf, 0
        for i in range(idx, len(nums)):
            base += nums[i]
            if (i, k-1) in dp:
                if base > dp[(i, k-1)]: 
                    break
            res = min(res, max(base, self.helper(dp, table, nums, i+1, k-1)))
        dp[(idx, k)] =res
        return dp[(idx, k)]
    def splitArray(self, nums: List[int], k: int) -> int:
        dp = dict()
        table = [0]
        for n in nums:
            table.append(table[-1]+n)
        return self.helper(dp, table, nums, 0, k)
'''
1. Problem
    - Given an integer array nums and an integer k
    - nums into k non-empty subarrays such that the largest sum of 


                   0. 1. 2. 3. 4. 5
    nums        : [2, 3, 1, 2, 4, 3]
    dp          : {F, D, D, 9, 7, 3})
    



    dp          : [1, 4, 4]
    ndp         : [3, x, ]

    (0, 2, 0)   : 6
    (1, 2, 0)   : 5
    (2, 2, 0)   : 3

    <gap is 1>
    (1, 2, 1)   : base + (2, 2, 0)
    (0, 2, 1)   : base + (1, 2, 0)
                : base + (2, 2, 0)


    <gap is 2>
    (0, 2, 2)   : base + (1, 2, 1)
                : base + (2, 2, 1)
    

    --------------------------------

    <gap is 0>
    dp[0]   : 6
    dp[1]   : 5
    dp[2]   : 3

    <gap is 1>
    dp[0]   :
    dp[1]   : 
    dp[2]   : impossible => !!!

    for g in ~~:
        for i in range(len(nums)-g):
            base = 0
            for k in range
                base += nums[k]
                ndp[i] = max(base,  dp[k+1])
        dp = ndp
    return min(dp)






    <gap is 0>
    (0, 0, 1)       : 1
    (1, 1, 1)       : 2
    (2, 2, 1)       : 3
    (0, 1, 1)       : 2
    (1, 2, 1)       : 3
    (0, 2, 1)       : 3

    <gap is 1>
    (0, 0, 2)       : impossible
    (0, 1, 2)       : (0, 0, 1), (1, 1, 1)
    (1, 2, 2)       : (1, 1, 1), (2, 2, 1)

    <gap is 2>
    (0, 2, 3)       : 


    nums        : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    <gap is 0>
    ~~~

    <gap is 1>
    (0, 9, 2)   : (0, )


    for g in gap:
        ndp = dict()
        for i in range(len(nums)):
            base = 0
            for k in range(i, len(nums)):
                base += nums[k]
                ndp 


                    
                   0. 1. 2. 3. 4. 5
    nums        : [2, 3, 1, 2, 4, 3]

    sum(nums[0:])
    nums 

    ([1], x=0, k=1)

                 i
            ([1, 2], 2)
                res     : 2
                base    : 3
        max(1, d([2], 1)=>2)=>2      max(3, d([], 1)inf)=>inf
            /

1. Problem 
    - Given an intger array nums
    - k split nums to k non-empty subarray such that largest sum of any subarray is minimized!

2. TCs
    tc1)
    nums    : [7, 2, 5, 10, 8]
    k       : 2
    res     : [7, 2, 5], [10, 8]
            : 18

    tc2)
    nums    : [1, 2, 3, 4, 5]
    k       : 2
    res     : [1, 2, 3] / [4, 5]
            : 9

    tc3)
    nums    : [1, 2, 3]
    k       : 2
    res     : 3 
            : [1, 2] / [3]
            : [1] [2, 3]

3. Brain Storming
    a) split
        => find the largest ! and get the smallest


                d([1, 2, 3], 2)
                /                       \
            min(1, d([2, 3], 1))        min(1+2, d([3], 1))


            if not nums:
                return math.inf

            if k == 1:
                return sum of nums ??
            
            base = 0
            for i in range(len(nums)):
                base += nums[i]
                res = min(res, max(base, d(nums[i+1:], k-1)))
            return res

                      i
                   0. 1. 2
                d([1, 2, 3], k=3)
                    base    : 3
            max(1, d([2, 3], 2))3        max(3, d([3], 2))
                base    : 5                     base    : 3
                /               \                               /
            max(2, d([3], 1))3   max(5, d([], 1)) inf           max(6, d([], 1))
            

'''
21600