Форум программистов, компьютерный форум CyberForum.ru

Динамическо программирование - C++

Восстановить пароль Регистрация
 
Rakaddar
0 / 0 / 0
Регистрация: 23.03.2009
Сообщений: 14
27.04.2009, 10:28     Динамическо программирование #1
Помогите пожалуйста решеть динамическим программированием задачу Лесенки. Заранее спасибо. Я просто не могу понять логику динамики в этой задаче

Добавлено через 23 часа 35 минут 39 секунд
решил сам
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
using namespace std;
 
int lesenka(int N,int min){
    int sum=0;
    for (int i=min;i<=N;i++){
        if(i==N){sum++;continue;}
        sum+=lesenka(N-i,i+1);  
    }
 
    return sum;
}
 
main () {
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);   
    int N;
    cin>>N;
    cout<<lesenka(N,1);
    cin>>N;
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.04.2009, 10:28     Динамическо программирование
Посмотрите здесь:

программирование на С C++
C++ Программирование на С
C++ Программирование на С++
C++ Программирование на С++
Программирование на C++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Monte-Cristo
 Аватар для Monte-Cristo
2805 / 1370 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
27.04.2009, 10:32     Динамическо программирование #2
а тут точно есть динамика?
Rakaddar
0 / 0 / 0
Регистрация: 23.03.2009
Сообщений: 14
11.03.2010, 12:42  [ТС]     Динамическо программирование #3
точно, можно перерешить этот рекурсивный перебор на динамику
Грымзик
 Аватар для Грымзик
2466 / 1443 / 31
Регистрация: 14.09.2009
Сообщений: 2,742
11.03.2010, 17:29     Динамическо программирование #4
Строишь таблицу: индекс столбца - количество кубиков (от 1 до N),
индекс строки - количество уровней. И элемент m[i][j] будет показывать
сколько лесенок высотой не более j можно построить из i кубиков.
Первая строка заполняется элементарно. Для заполнения i-го элемента
j+1 строки делаем так: суммируем все m[I][j], где I от i/2-1 (если i четное),
или от i/2 (нацело, если i нечетное) и до 1. И надо найти элемент m[N][N].
Yandex
Объявления
11.03.2010, 17:29     Динамическо программирование
Ответ Создать тему
Опции темы

Текущее время: 23:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru