Dynamic Programming: Fibonacci
Recently I watched an interesting video in youtube, the vbloger use calculating Fibonacci number to explain dynamic programming
after watch this video, I decide to write it down in English, also for practice my written English
ok, in this article, we will assume you already know what's Finabonacci number
commonly, we always use recursion to get the number, it's pretty easy to implement it
Recursion:
int Fib(int n)
{
if (n <= ) return ;
return Fib(n - ) + Fib(n - );
}
This is also the example when we learn recursion
the time complexity is O(X=2^n), it's calcualted like this
Fib(n) once
Fib(n -1) once
Fib(n-2) twice
Fib(n-3) Third
the total time is equal = 1+2+3...+(n - 1) = 2^n
this approach works for most of cases, but it's no effective and will cause stack over exception if the number is big, because there's call stacks
it cost really long time when I set n = 100
so we need to improve the recursion
we can see some numbers are calculated multiple times
for instance, Fib(5) = Fib(4) + Fib(3), Fib(4) = Fib(3) + Fib(2), Fib(3) will be calculated twice
Let's think about an approach to avoid it
Recursion and Memoize
in this appraoch, we will store the number when it's calculated
int Fib(int n, int[] memoized)
{
if (memoized[n] != ) return memoized[n];
if (n <= ) return ;
int f = Fib(n - ) + Fib(n - );
memoized[n] = f;
return f;
}
ok, we will only calculate once for one number, and the time complexity is O(n)
however there are still lots of call stack while calculating
the above 2 approaches are calculated from top to bottom, from n, n-1,...,1
How about calculate from bottom, just like the exmaple number see, 1,1,2,3,5,6...
Bottom Up
int Fib(int n)
{
if (n <= ) return ;
var memoized = new int[n + ];
memoized[] = ;
memoized[] = ;
for (int i = ; i <= n; i++)
{
memoized[i] = memoized[i - ] + memoized[i - ];
}
return memoized[n];
}
in this approach, we calcuate from bottom to up, altthough we add extra space for new array, but there are not so many call stacks, it's effective
The time complexity is also O(n)
ok, this is the summary of the video, I also found a video which explain dynamic programming by MIT
Please also find this video for reference
Dynamic Programming I: Fibonacci, Shortest Paths
最新文章
- echart折线图小知识
- 转:nginx基础概念(request)
- 【转】 Linux 线程同步的三种方法
- PAT (Basic Level) Practise:1033. 旧键盘打字
- Java 操作Excel 之Poi(第一讲)
- java反射1
- Resource is out of sync with the file system的解决办法
- UVa 10684 - The jackpot
- javascript设计模式详解之命令模式
- 浅谈canvas绘画王者荣耀--雷达图
- TF中conv2d和kernel_initializer方法
- 云计算openstack共享组件(2)——Memcache 缓存系统
- word交叉引用公式编号时和连公式一起引用
- android 设置LOGO和app名称
- window下git的下载
- Jdk提供的动态代理示例
- vue-router2.0 初学--动态赋值
- CentOS7图文安装教程
- BeanPostProcessor使用心得
- [BZOJ1975][SDOI2010]魔法猪学院(k短路,A*)