ПРОШУ ПОМОГИТЕ С++

Question

ПРОШУ ПОМОГИТЕ С++

leyla nuriyeva Ученик (86), открыт 3 недели назад

Лесенкой называется набор кубиков, в котором каждый горизонтальный слой содержит меньше кубиков, чем слой под ним.
Подсчитать количество различных лесенок, которые могут быть построены из N кубиков.
Входные данные

1
Результат работы

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

3
Результат работы

2

Answer 1

Один из вариантов решения этой задачи на C++:

#include <fstream>
using namespace std;

int get_count(int prev_level, int n) {
if (0 == n) return 1;
int count = 0;
for (int level = 1; level < prev_level; ++level) {
count += get_count(level, n - level);
}
return count;
}

int main() {
ifstream ifst("input.txt");
ofstream ofst("output.txt");
int n, count = 0;
ifst >> n;
for (int level = 1; level <= n; ++level) {
count += get_count(level, n-level);
}
}
В функции main выполняется генерация кубиков в первом уровне. В нём может быть от 1 до n кубиков. Функция get_count возвращает единицу, если количество кубиков равно нулю — то есть лесенку удалось сгенерировать. Для остальных случаев запускается рекурсивная функция с различными наборами данных, уменьшая количество кубиков на текущем уровне и увеличивая на следующем.

Answer 2

 #include <iostream> 
#include <vector> 
 
using namespace std; 
 
int countLadders(int n) { 
    vector<int> dp(n + 1, 0); 
    dp[0] = 1; 
 
    for (int i = 1; i <= n; ++i) { 
        for (int j = 1; j <= i; ++j) { 
            dp[i] += dp[i - j]; 
        } 
    } 
 
    int result = 0; 
    for (int i = 1; i <= n; ++i) { 
        result += dp[n - i]; 
    } 
     
    return result; 
} 
 
 
int main() { 
    int n; 
    cin >> n; 
    cout << countLadders(n) << endl; 
    return 0; 
}