Readme

2218.Maximum-Value-of-K-Coins-From-Piles

本题的动态规划算法本身不难想到，关键在于时间复杂度的分析。

因为我们对所有的pile依次处理，所以需要一个下标来表示pile的index。另外因为所能摘取coins总数目有限制，所以我们需要第二个下标来表示当前摘取的coins数目。即dp[i][j]表示截止到第i个pile，总共摘取j个coins的最大价值。

状态转移方程的着眼点自然就是第i根pile。我们能控制的就是该pile取几个coins。所以我们需要遍历对该pile的行动方案（即取0个，取1个，取2个，... ）

所以本题的状态转移方程就是：

dp[i][j] = max{dp[i-1][j-t] + pilesVal[i][t] }  where t= 0,1,2,...,len(piles[i])

其中pilesVal[i][t]就是第i根pile取t个硬币的收益，这个是可以提前计算好的。

显然，这里似乎需要三层循环：

for (int i=0; i<n; i++)
  for (int j=0; j<=k; j++)
    for (int t=0; t<=min(j, piles[i].size()); t++)
      dp[i][j] = max(dp[i][j], dp[i-1][j-t]+piles[i][t]);

那么总的时间复杂度是多少呢？看上去是o(N*K*K)，但是题目所给的数据量显然不支持这么大。这是怎么回事呢？

事实上第一层循环和第三层循环可以合并起来分析。我们对于每根pile（即变量i），都遍历它的硬币个数（即变量t）。将i和t全部遍历一遍，其实就是将所有pile的所有硬币遍历一遍。而题目中给出了所有pile的硬币总数不超过2000，所以本题实际的时间复杂度是o(K*2000).