c语言：用迭代法解决递归问题

题目：

---

 

解释：题目的意思就是用迭代法的空间和时间复杂的太高了，需要我们减小空间与时间的复杂度，我就想到了迭代法，思路和代码如下：

#include <stdio.h>
//这里是递归法转迭代法
int main()
{int x,i;scanf("%d",&x);long long a[x+1];//创建一个范围较大的数组，为避免溢出，多+1for(i=0;i<x+1;i++){if(i<3){a[i]=i;//如：i=0,a[0]=0;a[1]=1;a[2]=2；//数组下标等于数值}else{a[i]=a[i-3]+2*a[i-2]+3*a[i-1]//如：输入3，就是a[3]=a[0]+2*a[1]+3*a[2]}                               //    输入4，就是a[1]+2*a[2]+3*a[3]//    以此类推，因为大于等于a[3]的数组的已经有值了，不会创建新的空间，所以空间复杂度小}                                  //    且不会像递归那样，重复计算例如a[3]，a[4]的次数，这样迭代法的时间复杂度和空间复杂的都比较小printf("%lld",a[x]);
}

 

---

效果展示：