think about fibonacci
a fibonacci series is like
Code: Select all
1 1 2 3 5 8 13 ...
you may try recursion
Code: Select all
fib(int n){
if(n==1||n==2)return 1;
else return fib(n-1)+fib(n-2);
}
Code: Select all
fib(5)= fib(4) + fib(3)
fib(4) = fib(3) + fib(2) fib(3)=fib(2)+fib(1)
fib(3)=fib(1)+fib(2)
Code: Select all
5
/ \
4 3
/ \ / \
3 2 2 1
/ \
2 1
fib(3) calculated 2 times
fib(2) 3 times
fib(1) 2 times
these overlapping should be optimized by dp
see DP solution here using an array fib[n]
Code: Select all
fib[1]=fib[2]=1;
for(j=3;j<=n;j++)fib[j]=fib[j-1]+[j-2]
do you understand this sample of DP approach?
OH yes you may visit here
http://online-judge.uva.es/board/viewtopic.php?t=10565
some more discussion is going there