斐波那契数列规划题题解

509. 斐波那契数

/*
动态规划入门题：
1.
dp数组含义：存放斐波那契数。
dp[i]:存放第i个斐波那契数。
2.
递推公式
3.
dp数组的初始化
4.
遍历顺序
5.
打印
*/

int fib(int n)
{
    if (n == 0 || n == 1)
        return n;/**/

    //其实都只要维护三个值就好：dp[0],dp[1],sum
    int i, dp[31] = { 0 };
    dp[0] = 0;/*该题注意*/
    dp[1] = 1;
    for (i = 2; i <= n; i++)//注意i的起始值和最后的值
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}