A programação dinâmica guarda a resposta de uma pergunta menor para que as escolhas seguintes possam reutilizá-la. Comece escrevendo o que um estado significa. Uma contagem de rotas, um custo mínimo e um indicador de alcançabilidade de sim ou não precisam de valores base diferentes, mesmo que seus loops pareçam semelhantes. Zero é um custo válido, mas não é uma contagem válida para uma rota vazia que precisa servir de ponto de partida para as rotas seguintes.
Vá das dependências para a ordem de iteração. Fichas reutilizáveis podem estender repetidamente um total menor. Uma caixa indivisível não pode: atualizar as somas de subconjuntos para baixo impede usar essa caixa duas vezes. Para uma subsequência estritamente crescente, um conjunto compacto dos melhores valores finais substitui uma tabela de estados quadrática.
Antes de programar, acompanhe a menor entrada não vazia e a entrada vazia. Depois de programar, explique por que cada transição representa uma escolha válida e por que nenhuma escolha se perde. O último exercício aplica a ideia de estado a uma divisão de carga, e não a uma contagem de caminhos.
Escolha o significado dos estados e as transições para escolhas ordenadas, totais ótimos e alcançabilidade.