in Algorithms edited by
1,132 views
2 votes
2 votes

in Algorithms edited by
1.1k views

4 Comments

oh sorry i misinterpreted the question here they are asking the number of distinct function calls see if you draw a tree you will find that many of the calls are repeating they wont be evaluated again as they are stored in array using the memotization in dp but i still think the answer the would be 10 as you draw tree the distinct function calls will be f(12), f(10),f(9),f(8),f(7),f(6),f(5) , f(4),f(3),f(2) may i am missing something let me know if anything
0
0
From F(2), F(3) there should be 2 more calls..
0
0
Will we consider T(12), T(1) and T(0)?
0
0

1 Answer

4 votes
4 votes
Best answer
okay,it can be solved using Dynamic Programming

and once one is computed, it can be easily found by going through the table.

and we can write it like

T(12)=T(10)+T(9)

T(10)=T(8)+T(7)

T(9)=T(7)+T(6)

T(8)=T(6)+T(5)

T(7)=T(5)+T(4)

T(6)=T(4)+T(3)

T(5)=T(3)+T(2)

T(4)=T(2)+T(1)

T(3)=T(1)+T(0)

T(2)=T(0)+T(-1)

We need one function call for each unique T(x)

here we need function calls T(-1),T(0),T(1),T(2,)T(3),T(4),T(5),T(6),T(7),T(8),T(9),T(10),T(12)

13 function calls

so it should be the answer
selected by

4 Comments

ya, they did the same! i did table manner, they did tree approach! do not worry. Same thing.Even they missed something in last level
0
0
ok..actually they did not count all function calls, and counted T(5) twice, so I assumed it to be wrong.
0
0
^ they r consistent :P
0
0