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

@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();
    }
}

Новые блоги и статьи Все статьи Все блоги /
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .

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

	Лесенка - динамическое программирование 19.08.2009, 09:48. Показов 31390. Ответов 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 1980 / 836 / 115 Регистрация: 01.10.2012 Сообщений: 5,199 Записей в блоге: 2
	10.04.2018, 08:10
	Не вникал в обсуждение, может это уже предлагали. Если "динамикой" то я бы считал/хранил ключи как пару "число кубиков на данном слое" + "число оставшихся кубиков". Ну и конечно, отсечка - число оставшихся <= суммы арифметической прогрессии 0