当前位置:   article > 正文

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

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

题目

读题

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

列出前五项

F(0)F(1)F(2)F(3)F(4)
F(n)01123
F(n-1)+F(n-2)1+01+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。

执行状态转移

返回最终解 

代码段

  1. #include<stdio.h>
  2. int fib(int n);
  3. int main()
  4. {
  5. int num;
  6. printf("Please enter the num:");
  7. scanf("%d",&num);
  8. printf("%d\n",fib(num)); //调用函数
  9. return 0;
  10. }
  11. int fib(int n)
  12. {
  13. int F[31];
  14. int i;
  15. F[0]=0;
  16. F[1]=1; //设定初始状态
  17. for(i=2;i<=n;i++)
  18. {
  19. F[i]=F[i-1]+F[i-2]; //执行状态转移
  20. }
  21. return F[n]; //返回最终解
  22. }

运行结果 

 

总结

1>动态规划步骤

2>设计状态

3>写出状态转移方程

4>设定初始状态

5>执行状态转移

6>返回最终解

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/573352
推荐阅读
相关标签
  

闽ICP备14008679号