Encuentra el no. de maneras de conseguir una suma n con todos los enteros positivos menores que n

Question

Para un número dado n, dicen 2 cuántas formas podemos obtener una suma 2 utilizando números menores que 2.

1+1 = 2 
so, for 2 - just 1 way. 

n = 3 
1+1+1=3 
1+2=3 
so,for 3 - it is 2 ways 
n = 4 
1+1+1+1=4 
1+1+2=4 
1+3=4 
2+2=4 

so, for 4 - it is 4 ways 

¿Puede haber una patrón genérico/solución a esta pregunta?

Answer 1

Esto se conoce como Partition Problem y puede ver los detalles en el enlace al que se hace referencia. de wiki:

Una forma de conseguir una manija en la función de partición implica un función intermedia p (k, n), que representa el número de particiones de n usando sólo números naturales al menos tan grandes como k. Para cualquier valor dado de k, particiones contados por p (k, n) encajar en exactamente una de las siguientes categorías:

smallest addend is k 
smallest addend is strictly greater than k. 

El número de particiones que satisfacen la primera condición es p (k, n - k) Para ver esto, imagine una lista de todas las particiones del número n - k en números de tamaño al menos k, luego imagine agregar "+ k" a cada partición en la lista. Ahora, ¿de qué se trata? Como una nota, uno puede usar esto para definir una especie de relación de recursión para la partición función en términos de la función intermedia, a saber

1+ sum{k=1 to floor (1/2)n} p(k,n-k) = p(n), 

El número de particiones que satisfacen la segunda condición es p (k + 1, n) desde una partición en partes de al menos k que no contiene partes de exactamente k debe tener todas las partes al menos k + 1.

desde las dos condiciones son mutuamente excluyentes, el número de particiones reunión cualquiera de las condiciones es p (k + 1, n) + p (k, n - k). La función recursiva definida es así:

p(k, n) = 0 if k > n 

p(k, n) = 1 if k = n 

p(k, n) = p(k+1, n) + p(k, n − k) otherwise. 

De hecho, usted puede calcular todos los valores por memoization, para evitar que las llamadas recursivas adicionales.

Editar: Como unutbu mencionado en su comentario, por fin, se debe restar el resultado de 1 a salida de ella, de hecho se calculan todos los valores P como enlace wiki, pero al final cuando se desea resultado de salida, Debe restarlo por 1.