首先来看看题目的要求：空间复杂度 O(1)，时间复杂度 O(n) ，本题也有时间复杂度 O(logn)的解法~~~
那么首先回忆一下斐波那契数列，作为dp的入门题，斐波那契作为数学和许多书中的动归入门题
相信递归的方程式对于大家而言并不难
就是dp[i]=dp[i-1]+dp[i-2];
然后不断递归下去~~~但是要注意了这里空间复杂度是有要求的
所以可以利用滚动数组的思想，不难发现递归方程式只有三项，其中一项未知数，然后剩下的两项可以在递归的时候动态保存
具体可以看代码~~ 
int main()
{
    int n;
    scanf("%d", &n);
    int a=1,b=1,sum=0,i;
    if(n<=2)
    {
        printf("1");
        return 0;
    }
    for(i=2; i<n; i++)
    {
        sum = a+b;
        a = b;
        b = sum;
    }
    printf("%d", sum);
    return 0;
}