O que é "dinâmico" na programação dinâmica?

Um dos meus idosos teve uma entrevista de emprego e ele foi perguntado por que é chamado de dinâmico. Ele não conseguiu responder e, depois de desistir, o entrevistador disse que não havia nada de dinâmico nisso, é chamado assim. Isso é difícil de acreditar.

Refere-se ao fato de que os subproblemas são resolvidos durante o tempo de execução e usados ​​para atingir a meta final? Como a alocação dinâmica de memória que acontece durante o tempo de execução?

[RESPONDA]

Eu deveria ter lido este artigo da wiki antes de fazer a pergunta, desculpe.

Sempre intuí que isso significava que algoritmos usando programação dinâmica pareciam editar o espaço do problema " dinamicamente " até que o problema pudesse ser resolvido com um algoritmo ganancioso.

Por exemplo, com o problema do tabuleiro de damas , o algoritmo de programação dinâmica edita toda a placa à medida que passa por ela e, finalmente, um algoritmo ganancioso pode ser usado (da mesma forma, com o algoritmo de caminho mais curto de Dijkstra, etc.).

Não tenho certeza se isso generaliza para todos os problemas de programação dinâmica.

Na verdade, não há nada de especial no nome "programação dinâmica"; a técnica em si é apenas sobre recursão inteligente desenrolando. Veja esta pergunta e veja a resposta @Jeffe, na qual é relatado que Belman escolhe esse nome para distrair intencionalmente.

Há uma história interessante aqui. Bellman foi pioneiro nesse paradigma. Mas, na verdade, essa era uma pesquisa matemática. Naquela época, o então secretário de Defesa era paranóico das palavras Pesquisa e Matemática (cara louco, né!). Bellman estava com medo de que a arte secreta ficasse furiosa com seu trabalho e, eventualmente, o colocasse em problemas. Então, para confundir um pouco as coisas, ele chamou de Programação Dinâmica , mas não há nada de 'dinâmico' nisso ..

Richard Bellman chamou de Programação Dinâmica nas palavras em Bellman

Passei o trimestre de outono (de 1950) na RAND. Minha primeira tarefa foi encontrar um nome para processos de decisão em vários estágios.

Uma pergunta interessante é: de onde veio o nome, programação dinâmica? Os anos 50 não foram bons anos para a pesquisa matemática. Tínhamos um cavalheiro muito interessante em Washington chamado Wilson. Ele era secretário de Defesa e, na verdade, tinha um medo e ódio patológico da palavra pesquisa. Não estou usando o termo de ânimo leve; Estou usando com precisão. Seu rosto seria difuso, ele ficaria vermelho e ficaria violento se as pessoas usassem o termo pesquisa em sua presença. Você pode imaginar como ele se sentiu, então, sobre o termo, matemático. A RAND Corporation era empregada pela Força Aérea, e a Força Aérea tinha Wilson como chefe, essencialmente. Por isso, senti que tinha que fazer algo para proteger Wilson e a Força Aérea do fato de que estava realmente fazendo matemática dentro da RAND Corporation. Qual título, qual nome, eu poderia escolher? Em primeiro lugar, eu estava interessado em planejar, em tomar decisões, em pensar. Mas planejar, não é uma boa palavra por várias razões. Decidi, portanto, usar a palavra "programação". Eu queria passar a ideia de que isso era dinâmico, de vários estágios, variando no tempo. Eu pensei, vamos matar dois coelhos com uma cajadada só. Vamos usar uma palavra que tenha um significado absolutamente preciso, ou seja, dinâmico, no sentido físico clássico. Ele também possui uma propriedade muito interessante como adjetivo e é impossível usar a palavra dinâmica em um sentido pejorativo. Tente pensar em alguma combinação que possivelmente lhe dê um significado pejorativo. É impossível. Assim, pensei que programação dinâmica era um bom nome. Era algo que nem mesmo um congressista poderia se opor.

Fonte: Olho do furacão, Richard Bellman (autobiografia)