Dada a subestrutura ótima que encontramos

 - uma árvore binária de busca ótima T enraizada em r tem 
 
    - subárvore esquerda Tl e direita Tr que são ótimas, respectivamente, para os conjuntos de itens {1, ..., r-1} e {r+1, ..., n}

Temos o problema de não saber qual a raiz da árvore ótima, o que leva à questão:

 - quais as raizes possíveis para uma árvore que contém o conjunto {1, ..., n}?
 
   R: São n raízes possíves, i.e, todos os itens em {1, ..., n}
   
    - Isso indica que na nossa recorrência teremos que escolher a melhor solução entre as n possíveis

Outro ponto relevante é, quando estamos considerando uma raiz r, quantos/quais subproblemas temos que considerar?

   R: São dois subproblemas, um correspondendo à subárvore esquerda que contém os itens {1, ..., r-1} e outro correspondendo á subárvore direita que contém os itens {r+1, ..., n}
   
   - E como se relacionam os custos da árvore T enraizada em r com o custo de suas subárvores ótimas?
   
     R: C(T) = C(Tl) + C(Tr) + \sum_{k=1}^n pk
 
Escrevendo a relação de custo de uma árvore ótima para os itens {1, ..., n} considerando as n raízes possíveis e os subproblemas que surgem em cada caso, temos a seguinte recorrência

	A[1, n] = min_r=1,...,n {\sum_{k=1}^n pk + A[1, r-1] + A[r+1, n]}

    - com a ressalva de que A[i, j] = 0 se i > j



Note, no entanto, que nossa recorrência está escrita com os parâmetros 1 e n

 - Será que só precisamos nos preocupar com sequências de itens começadas em 1 e terminadas em n?
 
   R: Não. Para perceber isso, considere que vamos resolver o problema A[1, n] e note que para isso precisamos do valor de A[1, r] para todo r entre 1 e n. Vamos focar em um r' em particular e considerar o subproblema A[1,r']. Agora, repetindo o raciocínio, para resolver A[1, r'] precisamos do valor de A[k, r'] para todo k entre 1 e r'.
   
    - Portanto, nosso total de subproblemas corresponde a todos os intervalos contínuos {i, i+1, ..., j-1, j} com i <= j
	
	- Reescrevendo nossa recorrência na forma geral, para todo 1 <= i <= j <= n temos que
	
	  A[i, j] = min_r=i,...,j {\sum_{k=i}^j pk + A[1, r-1] + A[r+1, n]}
	  
       - lembrando da nossa convenção de que A[i, j] = 0 se i > j