Лесенка - динамическое программирование

@jds_07 · Регистрация: 12.03.2009

Студворк — интернет-сервис помощи студентам

Здраствуйте. У меня есть одна классическая задачка про Лесенку.

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

Входные данные
Во входном файле INPUT.TXT записано натуральное число N (1 ≤ N ≤ 100) – количество кубиков в лесенке.

Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести число лесенок, которые можно построить из N кубиков.

Примеры
INPUT.TXT OUTPUT.TXT
3 2
6 4

Я решил эту задачку с помощью грубого перебора и проходит тесты. Но я слышал что есть и другое эффективное решение с помощью динамическое программирование. Помогите решить.

@Ёрик · 27.08.2009, 10:17

Это вообще называется диаграмма Юнга.

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.io.PrintWriter;
import java.util.Scanner;
 
public class Stairs {
 
/**
* @param args
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);
int n = in.nextInt();
long[] q = new long[n + 1];
q[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = n; j >= i; --j) {
q[j] += q[j - i];
}
}
out.print(q[n] - 1);
in.close();
out.close();
}
 
}

@g-man · 16.11.2010, 22:01

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <string>
 
using namespace std;
int m[101][101];
 
int main()
{
    int n;
 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    cin >> n;
 
    for(int i = 0; i < n+1; i++)
    {
        m[0][i] = 0;
        m[1][i] = 1;
    }
    for(int i = 0; i < n+1; i++)
        m[i][0] = 0;
 
    for(int i = 1; i < n+1; i++)
    {
        for(int j = 1; j < n+1; j++)
        {
            if(i == 1)
                break;
            else if(i == j)
                m[i][j] = m[i][j-1] + 1;
            else if(j > i)
                m[i][j] = m[i][j-1];
            else
                m[i][j] = m[i][j-1] + m[i-j][j-1];
        }
    }
 
    cout << m[n][n];
 
    return 0;
}

@Ёрик · 17.11.2010, 14:42

Сообщение от g-man

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <string>
 
using namespace std;
int m[101][101];
 
int main()
{
    int n;
 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    cin >> n;
 
    for(int i = 0; i < n+1; i++)
    {
        m[0][i] = 0;
        m[1][i] = 1;
    }
    for(int i = 0; i < n+1; i++)
        m[i][0] = 0;
 
    for(int i = 1; i < n+1; i++)
    {
        for(int j = 1; j < n+1; j++)
        {
            if(i == 1)
                break;
            else if(i == j)
                m[i][j] = m[i][j-1] + 1;
            else if(j > i)
                m[i][j] = m[i][j-1];
            else
                m[i][j] = m[i][j-1] + m[i-j][j-1];
        }
    }
 
    cout << m[n][n];
 
    return 0;
}

Вроде, рабочий вариант, но слишком длинно и куча условий. Автор просил использовать динамическое программирование. Выше мой пример, там 3 строки (2 цикла и 1 оператор БЕЗ условий).

@g-man · 17.11.2010, 17:26

А у меня не динамика?

@Ёрик · 17.11.2010, 18:18

Я бы сказал слишком длинно.

@Wanee · 04.02.2011, 13:37

Это рекуссия. И решать нужно рекурсивно. После олимпиады выложу решение.

@Tema Novichkov · 11.10.2016, 16:38

g-man, Доброго времени суток, столкнулся с аналогичной задачей, но, увы, не совсем понимаю Ваше решение, не могли бы Вы его прокомментировать.

@Николаев Михаил · 03.04.2018, 18:29

Помогите пожалуйста. Столкнулся с этой же задачей, но её надо написать на питон(python). Не могли бы вы перевести с С++ на питон?

@Shamil1 · 04.04.2018, 17:23

Сообщение от Николаев Михаил

Не могли бы вы перевести с С++ на питон?

Это в раздел по Питону (или по С++).

@Igor3D · 10.04.2018, 08:10

Не вникал в обсуждение, может это уже предлагали. Если "динамикой" то я бы считал/хранил ключи как пару "число кубиков на данном слое" + "число оставшихся кубиков". Ну и конечно, отсечка - число оставшихся <= суммы арифметической прогрессии

@Shamil1 · 18.04.2018, 10:43

Нет смысла заполнять матрицу. Например, для 10 в треугольной матрице будет 55 значений, из которых реально нужны только 8. Поэтому просто кэшируем результаты промежуточных вычислений.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Solve(int n)
{
    var d = new Dictionary<ValueTuple<int, int>, int>{ {(0,0), 1} };
    int f (int m, int maxwidth)
    {
        if (!d.TryGetValue((m, maxwidth), out int res))
        {
            for (int w = maxwidth; w * (w + 1) / 2 >= m; w--)
                res += f(m - w, Math.Min(m - w, w - 1));
            d.Add((m, maxwidth), res);
        }
        return res;
    };
    return f(n,n);
}

@Diom · 11.07.2023, 18:05

Тут следую логике, что на каждую следующую ступеньку вниз требуется +1 кирпич. Счет начинается с одного кирпича. Рекурсия.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Lestnica
{
   static int y;
   static int Schet(int x)
    {         
        if (y == 0) { x--;}       
        if (x > 0)  { y = y + 1; x = Schet(x - y);}
        return y;
    }
    static void Main()
    {     
       Console.WriteLine(Schet(10));
       Console.ReadLine();
    }
}

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@jds_07 28 / 27 / 11 Регистрация: 12.03.2009 Сообщений: 85

	Лесенка - динамическое программирование 19.08.2009, 09:48. Показов 30838. Ответов 51 Метки нет (Все метки) Здраствуйте. У меня есть одна классическая задачка про Лесенку. Лесенка Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий. Требуется написать программу, вычисляющую число лесенок, которое можно построить из N кубиков. Входные данные Во входном файле INPUT.TXT записано натуральное число N (1 ≤ N ≤ 100) – количество кубиков в лесенке. Выходные данные В выходной файл OUTPUT.TXT необходимо вывести число лесенок, которые можно построить из N кубиков. Примеры INPUT.TXT OUTPUT.TXT 3 2 6 4 Я решил эту задачку с помощью грубого перебора и проходит тесты. Но я слышал что есть и другое эффективное решение с помощью динамическое программирование. Помогите решить. 0

@g-man 9 / 9 / 1 Регистрация: 02.04.2010 Сообщений: 25
	17.11.2010, 17:26
	А у меня не динамика? 0

@Ёрик 47 / 47 / 3 Регистрация: 07.01.2009 Сообщений: 297
	17.11.2010, 18:18
	Я бы сказал слишком длинно. 0

@Wanee 54 / 54 / 23 Регистрация: 02.02.2011 Сообщений: 436
	04.02.2011, 13:37
	Это рекуссия. И решать нужно рекурсивно. После олимпиады выложу решение. 0

@Tema Novichkov 0 / 0 / 0 Регистрация: 15.10.2015 Сообщений: 1
	11.10.2016, 16:38
	g-man, Доброго времени суток, столкнулся с аналогичной задачей, но, увы, не совсем понимаю Ваше решение, не могли бы Вы его прокомментировать. 0

@Николаев Михаил 0 / 0 / 0 Регистрация: 03.04.2018 Сообщений: 5
	03.04.2018, 18:29
	Помогите пожалуйста. Столкнулся с этой же задачей, но её надо написать на питон(python). Не могли бы вы перевести с С++ на питон? 0

@Igor3D 1963 / 819 / 114 Регистрация: 01.10.2012 Сообщений: 4,770 Записей в блоге: 2
	10.04.2018, 08:10
	Не вникал в обсуждение, может это уже предлагали. Если "динамикой" то я бы считал/хранил ключи как пару "число кубиков на данном слое" + "число оставшихся кубиков". Ну и конечно, отсечка - число оставшихся <= суммы арифметической прогрессии 0