Question

Даю 20баллов!!! Только на C++!!!!!

Количество разбиений на слагаемые

Дано натуральное число N. Найдите количество его разбиений на натуральные слагаемые. Два разбиения, отличающиеся только порядком слагаемых, будем считать за одно.


Например, для N=5 существует 7 различных разбиений:


5=5

5=4+1

5=3+2

5=3+1+1

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

Входные данные


Задано единственное число N≤30.


Выходные данные


Выведите количество различных разбиений на слагаемые.


Примеры

Ввод 5

Вывод 7

В помощь видео!!!!
youtube
/watch?v=MrdTbJ5zKsQ

Answer 1

Ответ:

#include <stdio.h>

int d[100][100];

int dec(int n, int k) {

 if ( n >= 0 && k >= 0 && d[n][k] > 0 ) return d[n][k];

 if ( n < 0 ) return 0;

 if ( n <= 1 || k == 1 ) return 1;

 d[n][k] =  dec(n, k-1) + dec(n-k, k);  

 return d[n][k];

}

int main() {

 int m, i, j;

 scanf("%d", &m);

 for (i = 0; i < m; i++) {

   for (j = 0; j < m; j++) {

     d[i][j] = -1;

   }

 }

 printf("%d\n", dec(m, m));

 return 0;

}

Объяснение:

удачи на сириусе))))