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

[DRGNforce]

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

(рис)

                7
              3  8  
            8  1  0
          2  7  4  4
        4  5  2  6  5

Каждый шаг на пути может осуществляться вниз по диагонали вправо
Число строк в тругольнике >1 и <=100.
Треугольник составлен из целых чисел от 0 до 99.
Решение. Это типичная задача на метод динамического программирования. Пусть A[i,j] озночает j-ое число в i-ой строке треугольника, а S[i,j] наибольшую сумму чисел на пути от вершины треугольника до этого числа. Очевидны соотношения:
S[1,1]=A[1,1]
S[i,j]=max(S[i-1,j],[S[i-1,j-1])+A[i,j],(1<= j<=N,j>1)
Пологаем, что числа S[i,0] и S[i,i+1] (1<= i<=N) равны нулю. Ответ на задачу можно узнать, вычислив

Max (S[N,j])
1<=j<=N
Для приведенного в условии задачи примера числа S[i,j] будут такими (максимальное число в последней строке является ответом):

               7
           10  15
        18  16  15
      20  25  20  19
   24  30  27  26  24

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



P.S: Рисунок должен быть как пирамида. (тут я не смог так делать)

[Serge_Bliznykov]

или я что-то не понял, или одно из двух.
Зачем Вам полный перебор, если Вы уже имеете решение (ведь заполненная матрица S и является решением!)
находите максимальное значение в строке основания: S[n, maxInd]
Например, для вашей матрицы maxInd будет 2.
S[5, 2] у него есть две точки, из которых можно в данную точку прийти
S[4, 1] и S[4,2] - берём max(20, 25) = 25 = S[4,2]
в неё можно прийти из S[3,1] и S[3,2] - берём max( 18, 16 ) = 18 = S[3,1]
в неё можно попасть только из S[2,1]
в неё можно попасть только из S[1,1]
записываем полученный путь S[1,1] S[2,1] S[3,1] S[4,2] S[5,2]
этот же путь в исходной матрице A[1,1] A[2,1] A[3,1] A[4,2] A[5,2]
7 3 8 7 5
7 + 3 + 8 + 7 + 5 = 30

[DRGNforce]

на паскале как будет? помогите

[Serge_Bliznykov]

чем помочь? Написать полностью за Вас?!?! Так это не помощь называется!
Представьте, пригласили Вы соседа, ну, например, огород Вам помочь вскопать. Он копает, Вы сидите, наблюдаете... Если он спросит, почему Вы сидите, не копаете ваш же огород, Вы скажете, что Вы копать не умеете, поэтому скромно посидите в сторонке, а он пусть Вам "помогает"... Аналогия, надеюсь, понятна?

Ну и,
во-первых, это будет "медвежья" услуга (Вы же после этого Паскаль лучше знать не станете!)

а во-вторых, не думаю, что кто-то будет бесплатно с нуля писать Вам программу (а потом ещё и "разжёвывать", как же она работает)...

Начните делать, обеспечьте заполнение пирамиды начальными значениями, ПОПЫТАЙТЕСЬ (хотя бы) заполнить структуру S (формулы заполнения у Вас же уже есть) и Вам обязательно помогут.

Успехов в обучении...

[programmerhpkk]

Сообщение от DRGNforce

на паскале как будет? помогите

На паскале будет примерно так:
program triangle;
var {описание переменных}
Begin
{Реализация алгоритма программы}
end.
По желанию можно добавить процедуры, функции и т.д.