leetcode：813. 最大平均值和的分组（dp）--（矩阵连乘升级版）

题目：

分析：

刚开始想用矩阵连乘的思路，但苦于没法设置数组。k是几就应该设置成几维的。
官方题解给出如下：

不论你分成多少份，我都可以用二维的数组来划分！

代码：

double D[200][200][200];
double f(vector<int> A,int x,int y,int k)
{//表示的含义是A的 x-y范围内分成k份 
 if(y-x+1<k) return 0;//无法分 
  if(D[x][y][k]) return D[x][y][k];
  if(k==1) 
  {
   int all=0;
   for(int i=x;i<=y;i++) all+=A[i];
   D[x][y][k]=all*1.0/(y-x+1);
   return D[x][y][k];
  }
  int all=0;
  for(int i=x;i<y;i++)
  {
   D[x][y][k]=max(D[x][y][k],f(A,x,i,1)+f(A,i+1,y,k-1));
  }
  return  D[x][y][k]; 
}
int main()
{
 memset(D,0,sizeof(D));
 vector<int> A;
 int k;
 f(A,0,A.size()-1,k);
}