Dynamic programming

Question

My answer came out to be 13:

because when we will compute T(13)

{

as we are using Dynamic programming , it will have to compute value of T(12),T(11),…...T(2) only once(as it will store it and reuse it)

so the stack size will be 1 (for T(13))+11  (for T(12),T(11),…...T(2)) = 12…...(48/4)

}

will any one help me out

Comments

And what is kept in stack? @Nandkishor3939 Activation Records right?

---

I am concerned about:

"  for which value of n ?? "  is asked and not for "how many AR's"

---

When you call T(13) then t(13) → T(12) → t(11) → ….. → t(1) are on the stack => we have 13 Activation records on the stack each takes 4 Byte so 13 X 4 => 52 Bytes require for stack to call T(13) so 13 can’t be answer

Answer 1

I tried to solve like this.

Imagine(please imagine) we have T(4) and I have computed values of T(1) and T(0) only.

So we need to compute T(4) T(3) and T(2). And when it reach T(1)., T(4) T(3) and T(2) will be in stack. 

So the no of values present in the stack can be written as 4-2+1=3.(I am adding 1 in the eq because I am including T(2) too).

Now moving back to the question, suppose we have T(13). and in the question they have mentioned that they have computed values of T(1) and T(0). So using the same argument we can say that we have 

13-2+1=12 records in the stack which is the max. So 13 should be the answer.