Lembrando como descrevemos a solução ótima para G em função de soluções para subproblemas.

Uma solução ótima para G deve ser a melhor entre:

 - uma solução ótima em G' (G sem o último vértice)
 
 - vn + uma solução ótima em G" (G sem os dois últimos vértices)
 
Podemos escrever essa relação como uma recorrência:

 - A[n] = max{A[n-1], A[n-2] + w[vn]}



Apesar do algoritmo recursivo que derivamos diretamente levar tempo exponencial, observem:

 - o padrão e a quantidade de subproblemas com os quais temos que lidar

Apenas vértices do extremo direito do caminho são removidos

Assim, cada subproblema é um prefixo do caminho

Como o caminho original tem n vértices, temos Theta(n) diferentes subproblemas

De fato, o algoritmo recursivo gasta tempo exponencial por ficar recalculando inúmeras vezes os mesmos subproblemas.

E podemos torná-lo polinomial (linear, no caso) se 

 - guardarmos numa tabela o valor de um subproblema na primeira vez que o calcularmos
 
 - e sempre verificarmos essa tabela antes de recalcularmos um subproblema
 
Essa técnica é conhecida como memorização (memoization) e tem uma relação próxima com programação dinâmica.



Voltando à recorrência que obtivemos

 - A[n] = max{A[n-1], A[n-2] + w[vn]}

Vamos finalmente construir nosso algoritmo iterativo de programação dinâmica

 - para tanto vamos preencher o vetor de baixo para cima
 
 - seguindo a regra da recorrência

// supomos que o vetor vai de 0 até n, e os vértices de 1 até n
conjInd(G=(V,E), w) {
	A[0] = 0
	A[1] = w1
	para i = 2 até n
		A[i] = max{A[i-1], A[i-2] + w[vi]
	devolva A[i]
}

Corretude: Segue da subestrutura ótima e pode ser provada por indução.

Eficiência: O(n), pois o algoritmo só tem um laço principal e realiza um número de operações constante dentro deste.