<p>You are given an integer array <code>nums</code> and an integer <code>k</code>. You can partition the array into <strong>at most</strong> <code>k</code> non-empty adjacent subarrays. The <strong>score</strong> of a partition is the sum of the averages of each subarray.</p>

<p>Note that the partition must use every integer in <code>nums</code>, and that the score is not necessarily an integer.</p>

<p>Return <em>the maximum <strong>score</strong> you can achieve of all the possible partitions</em>. Answers within <code>10<sup>-6</sup></code> of the actual answer will be accepted.</p>

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

<pre>
<strong>Input:</strong> nums = [9,1,2,3,9], k = 3
<strong>Output:</strong> 20.00000
<strong>Explanation:</strong> 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5,6,7], k = 4
<strong>Output:</strong> 20.50000
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= k &lt;= nums.length</code></li>
</ul>

class Solution {
public:
// double solveRec(vector<int>&nums,vector<int>&prefix,int k,int s,int e)
// {
//     if(s>e)
//     {
//         return (double)0.0;
//     }
//     if(s==e)
//     {
//         return (double)nums[s];
//     }
//     if(k==0)
//     {
//         if(s!=0)
//         return ((double)prefix[e]-prefix[s-1])/(e-s+1);
//         else
//         return ((double)prefix[e]/(e-s+1));
//     }
//     double ans=0;
//     for(int i=s;i<=e;i++)
//     {
//         double a1=0,a2=0;

//         double left=solveRec(nums,prefix,0,s,i);
//         double right=solveRec(nums,prefix,k-1,i+1,e);
//         a1=left+right;
//         double left1=solveRec(nums,prefix,k-1,s,i);
//         double right1=solveRec(nums,prefix,0,i+1,e);
//         a2=left1+right1;
//         ans=max(ans,max(a1,a2));
//     }
//     return ans;
// }
double solveTab(vector<int>&nums,vector<int>&prefix,int k,int s,int e,vector<vector<vector<double>>>&dp)
{
    if(s>e)
    {
        return (double)0.0;
    }
    if(s==e)
    {
        return (double)nums[s];
    }
    if(k==0)
    {
        if(s!=0)
        return ((double)prefix[e]-prefix[s-1])/(e-s+1);
        else
        return ((double)prefix[e]/(e-s+1));
    }
    if(dp[k][s][e]!=-1)
    {
        return dp[k][s][e];
    }
    double ans=0;
    for(int i=s;i<=e;i++)
    {
        double a1=0,a2=0;

        double left=solveTab(nums,prefix,0,s,i,dp);
        double right=solveTab(nums,prefix,k-1,i+1,e,dp);
        a1=left+right;
        double left1=solveTab(nums,prefix,k-1,s,i,dp);
        double right1=solveTab(nums,prefix,0,i+1,e,dp);
        a2=left1+right1;
        ans=max(ans,max(a1,a2));
    }
     dp[k][s][e]=ans;
     return  dp[k][s][e];
}
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int>prefix(n,0);
        prefix[0]=nums[0];
        for(int i=1;i<n;i++)
        {
            prefix[i]=prefix[i-1]+nums[i];
        }
        // return solveRec(nums,prefix,k-1,0,n-1);
        vector<vector<vector<double>>>dp(k+1,vector<vector<double>>(n+1,vector<double>(n+1,-1)));
        return solveTab(nums,prefix,k-1,0,n-1,dp);
    }
};
42800