leetcode 509.斐波那契数 C语言 动态规划

从第三项开始，每一项是前两项的和，给定数n，求F(n)。

列出前五项

运用动态规划

设计状态：从第三项开始每一次求第n项都转移到求n-1项和n-2项

写出状态转移方程：F(n)=F(n-1)+F(n-2);

设定初始状态：当n=0、1时，F(0)=0,F(1)=1。

执行状态转移

返回最终解 

#include
int fib(int n);
int main()
{
    int num;
    printf("Please enter the num:");
    scanf("%d",&num);
    printf("%dn",fib(num));            //调用函数
    
    return 0;
}
int fib(int n)
{
    int F[31];
    int i;
    F[0]=0;
    F[1]=1;                            //设定初始状态
    for(i=2;i<=n;i++)
    {
        F[i]=F[i-1]+F[i-2];            //执行状态转移
    }
    return F[n];                       //返回最终解
}

1>动态规划步骤

2>设计状态

3>写出状态转移方程

4>设定初始状态

5>执行状态转移

6>返回最终解