algorithm - 如何求解 T(n) = T(n-1) + n^2？

<分区>

见标题。我正在尝试应用这个问题的方法:Easy: Solve T(n)=T(n-1)+n by Iteration Method .到目前为止我所拥有的是这个，但我不知道如何从这里开始:

T(n) = T(n-1) + n²

T(n-1) = T(n-2) + (n-1)² = T(n-2) + n² - 2n + 1

T(n-2) = T(n-3) + (n-2)² = T(n-3) + n² - 4n + 4

T(n-3) = T(n-4) + (n-3)² = T(n-4) + n² - 6n + 9

将 T(n-1)、T(n-2) 和 T(n-3) 的值代入 T(n) 得到:

T(n) = T(n-2) + 2n² - 2n + 1

T(n) = T(n-3) + 3n² - 6n + 5

T(n) = T(n-4) + 4n² - 12n + 14

现在我必须找到一种模式，但我真的不知道该怎么做。我得到的是:

T(n) = T(n-k) + kn² - ...???

最佳答案

我首先猜测，由于每个 T (n) 等于前一个加上一个正方形，因此 T (n) 是立方体。

写出 T(n) = an^3 + bn^2 + cn + d。

将其代入 T (n) = T (n - 1) + n^2 并求解 a、b、c。

显然 T (0) = d。

关于algorithm - 如何求解 T(n) = T(n-1) + n^2？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30738540/

相关文章：

c++ - 对每个递归结构的元素执行一些操作，而无需在 C++ 中向其添加方法