Recursive Formula and Time Taken

• Recursively,
  M[i,j]=

  

  

• Optimal Substructure

• We can recursively solve for
  M[1,n]=
  
  ,
  ,
  ,
  
  
  
• Time Complexity:

  

  

  Subtracting (I)-(II) yields

  

• Recursive Solution is exponential time
• Space O(n) stack depth.
• Overlapping subproblems: e.g. Recursion tree for M[1,4].
  26 recursive calls for just 10 subproblems
  

So we turn to dynamic Programming,

• the same formulation
• approach the problem bottom-to-top
• find a suitable table to store the sub-solutions.
  

  How many sub-solutions do we have?
  
  
  
  
  
  
  
  we need space