С++ задача про лесенки помогите пожалуйста.

С++ задача про лесенки помогите пожалуйста.

Для решения данной задачи можно использовать динамическое программирование.

Создадим массив dp размером N+1, где dp[i] будет хранить количество различных лесенок, которые можно построить из i кубиков.

Инициализируем dp[1] = 1, так как из одного кубика можно построить только одну лесенку.

Затем, для каждого числа i от 2 до N, будем перебирать количество кубиков в последнем слое лесенки. Пусть j - количество кубиков в последнем слое. Тогда количество лесенок, которые можно построить из i кубиков, будет равно сумме dp[i-j] для всех возможных значений j.

Таким образом, можно записать следующий код на C++:

include

using namespace std;

int main() { int N; cin >> N;

int dp[51] = {0};
dp[1] = 1;

for (int i = 2; i <= N; i++) {
    for (int j = 1; j < i; j++) {
        dp[i] += dp[i-j];
    }
}

cout << dp[N] << endl;

return 0;

}

Пример работы программы:

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

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

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

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