标签：11 code 2021.10 复杂度 sum DP

Candies

思路

朴素的算法
设\(f_{i,j}\)表示给前\(i\)个小朋友分\(j\)个糖的方案数，

\[f_{i,j}=\sum_{k=0}^{min(a[i],j)}f_{i-1,j-k} \]

注意到此时时间复杂度为\(O(n\times k^2)\)
想到用前缀和进行优化，设\(s_{i,j}\)表示\(\sum_{j=0}^{k}f_{i,j}\)
则\(DP\)转移方程

\[f_{i,j}=s_{i-1,j}-s_{i-1,j-a[i]-1}(j-a[i]-1\ge 0)\\ f_{i,j}=s_{i-1,j}(j-a[i]-1<0)\]

答案就是\(f_{n,k}\)

\(code\)

code
注，可以用滚动数组，优化空间复杂度

标签：11,code,2021.10,复杂度,sum,DP
From： https://www.cnblogs.com/GSNforces/p/18458691