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

题目

读题

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

列出前五项

	F(0)	F(1)	F(2)	F(3)	F(4)
F(n)	0	1	1	2	3
F(n-1)+F(n-2)			1+0	1+1	2+1

运用动态规划

设计状态：从第三项开始每一次求第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("%d\n",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>返回最终解