Dado um número N, encontre o número de maneiras de escrevê-lo como uma soma de dois ou mais números inteiros consecutivos
Aqui está oproblema que marcou comoprogramaçao dinamica (Dado um número N, encontre o número de maneiras de escrevê-lo como uma soma de dois ou mais números inteiros consecutivos) e exemplo 15 = 7 + 8, 1 + 2 + 3 + 4 + 5, 4 + 5 + 6
Eu resolvi com a matemática assim:
a + (a + 1) + (a + 2) + (a + 3) + ... + (a + k) = N
(k + 1) * a + (1 + 2 + 3 + ... + k) = N
(k + 1)a + k(k + 1) / 2 = N
(k + 1) * (2 * a + k) / 2 = N
Em seguida, verifique se N divisível por (k + 1) e (2 * a + k), posso encontrar resposta no tempo O (sqrt (N))
Aqui está minha pergunta: como você pode resolver issoprogramaçao dinamica ? e qual é a complexidade (O)?
P.S: com licença, se for uma pergunta duplicada. Eu procurei, mas posso encontrar