MadeEasy Subject Test: Algorithms - Dynamic Programming

Question

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

---

From F(2), F(3) there should be 2 more calls..

---

Will we consider T(12), T(1) and T(0)?

Answer 1

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

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

---

ok..actually they did not count all function calls, and counted T(5) twice, so I assumed it to be wrong.

---

^ they r consistent :P