急急急！大一C语言编程题降低时间复杂度？

这道题要求运行时间在1s内，现在一直是三秒左右，我是大一学生，样例能通过，可就是时间超限，要怎么修改可以降到一秒
代码如下：
#include
#include

int fun(int n) {
long int sum=0;
if(n==1)return 0;
else if(n==2)return 1;
else {
sum=fun(n-1)+2*fun(n-2)+pow(n,3)+2*n+1;
return(sum%1000000007);
}
}
int main() {
int m,n;
scanf("%d",&m);
for(int i=0; i<m; i++) {
scanf("%d",&n);
printf("%d\n",fun(n));
}
return 0;

}

int a = 0;
int b = 1;
for (int i = 2; i <= n; i++)
{
sum=b+2*a+pow(n,3)+2*n+1;
a = b;
b = sum%1000000007;
}

解释一下楼上，递归虽然好写，但每次开辟新的空间内存和时间花销很大，采用一重循环，将结果记录下来，每个n只需要计算一次
而递归f(n)需要f(n-1)，f(n-2)的值，而计算f(n-1)又一次需要f(n-2)的值，每个n会计算两次。