#include <iostream>
#include <vector>
using namespace std;
int countStaircases(int N) {
// Создаем двумерный массив dp размером (N+1) x (N+1) и заполняем его нулями
vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
// Инициализируем базовый случай
for (int k = 0; k <= N; ++k) {
dp[0][k] = 1; // 1 способ построить лесенку из 0 кубиков
}
// Заполняем массив dp по описанному выше рекуррентному соотношению
for (int n = 1; n <= N; ++n) {
for (int k = 1; k <= N; ++k) {
dp[n][k] = dp[n][k - 1];
if (n >= k) {
dp[n][k] += dp[n - k][k - 1];
}
}
}
// Ответ находится в dp[N][N]
return dp[N][N];
}
int main() {
int N;
cout << "Введите количество кубиков N: ";
cin >> N;
int result = countStaircases(N);
cout << "Количество различных лесенок: " << result << endl;
return 0;
}
#include <iostream>
#include <vector>
int main() {
int N;
std::cin >> N;
// dp[i][j] - количество способов представить число i с максимальным слагаемым j
std::vector<std::vector<int>> dp(N + 1, std::vector<int>(N + 1, 0));
// Инициализация: для числа 0 есть 1 способ разложения (пустое множество)
dp[0][0] = 1;
for (int sum = 1; sum <= N; ++sum) {
for (int last = 1; last <= sum; ++last) {
// Перебираем все возможные предыдущие слагаемые, которые меньше, чем текущее
for (int prev = last - 1; prev >= 0; --prev) {
dp[sum][last] += dp[sum - last][prev];
}
}
}
// Суммируем все варианты разбиений числа N
int result = 0;
for (int last = 1; last <= N; ++last) {
result += dp[N][last];
}
std::cout << result << std::endl;
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int countLadders(int N) {
// Создаем массив для хранения результатов
vector<int> dp(N + 1, 0);
dp[0] = 1; // 1 способ построить лесенку из 0 кубиков
// Перебираем количество кубиков
for (int i = 1; i <= N; ++i) {
// Перебираем возможные верхние слои
for (int j = 1; j <= i; ++j) {
dp[i] += dp[i - j];
}
}
return dp[N];
}
int main() {
int N;
cout << "Введите количество кубиков: ";
cin >> N;
int result = countLadders(N);
cout << "Количество различных лесенок: " << result << endl;
return 0;
}
Подсчитать количество различных лесенок, которые могут быть построены из N кубиков.
Входные данные
1
Результат работы
1
Входные данные
3
Результат работы
2