阶乘计算

题目描述
计算S=1！+2！+3！+ … +N！的值

输入描述:
输入一行，包含一个整数n (n <= 10)

输出描述:
输出一行，包含一个整数。

示例1
输入：2
输出：3

解题思路：
常规思路：通过分别计算S中每一项的阶乘，然后求和得到结果。但是这种方式的时间复杂度为 。
动态规划：从S中可以看出，第 i 项的阶乘等于第 i - 1 项阶乘乘上 i ，因此存在重叠子问题。可以考虑使用动态规划求解，可以使用长度为 n 的一维数组 dp 存储每一项的阶乘值，状态转移方程为：dp[i] = i * dp[i-1]，初始条件为：dp[0] = 1，则最终求和结果即为：sum(dp)。这样可以把时间复杂度降为： 。进一步观察状态转移方程可知，当前项只与前一项有关，因此，可以利用滚动数组的方法，将空间复杂度从 降到 。具体方式：声明两个变量 p、q，p 表示第 i 项阶乘，q 表示从第1项到第 i 项的累加和，则循环结束后 q 值即为题解。

C# 代码：

using System;
class Program
{
  static void Main()
  {
      string input;
      while ((input = Console.ReadLine()) != null)
      {
          int n = int.Parse(input);
          int res = 0, prod = 1;
          for(int i = 1; i <= n; i++){
              prod *= i;
              res += prod;
          }
          Console.WriteLine(res);
      }
  }
}