С++ Сложная задача

[sir.andrey]

Здравствуйте товарищи умные!!!
Помогите с задачкой,
хотя бы алгоритм подскажите, а то вообще мыслей нет!!!

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

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

[RUSt88]

хехе, писал я когда-то на Сях на первом курсе такое )))
обращайся )

[sir.andrey]

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

хехе, писал я когда-то на Сях на первом курсе такое )))
обращайся )

Ну что ж, буду рад вашей помощи!!!

[RUSt88]

ну пиши в асю тогда лучше )) договоримся о сроках и вознаграждении

[sir.andrey]

Ты ведь тоже был студентом!!!
Ты что не понимаешь??
Откуда у меня деньги???

[sir.andrey]

Ну помогите же!!!!

[LeBron]

Динамическое программирование на двухмерном массиве. Потом выбираем максимум из ответов для последней строки.

Или ответ для корня, если двигались в обратном порядке.

[__Demon__]

Так?

#include <iostream>
#include <stdlib.h>

template<int n>
void triangle(int a[][n])
{
	// Печать треугольника
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < (i + 1); j++)
		{
			std::cout << a[i][j] << ' ';
		}
		std::cout << std::endl;
	}

	// Подщитываем сумму в рёбрах
	int sum1 = 0;
	int sum2 = 0;
	int sum3 = 0;

	for (int i = 0; i < n; i++)
	{
		sum1 += a[i][0];
		sum2 += a[i][i];
		sum3 += a[n - 1][i];
	}

	// Печатаем максимальную сумму
	std::cout << std::endl << "Max = "
		<< std::max(std::max(sum1, sum2), sum3) << std::endl;
}


int main()
{
	int a[5][5] = {{7}, {3, 8}, {8, 1, 0}, 
		{2, 7, 4, 4}, {4, 5, 2, 6, 5}};

	triangle(a);

	system("PAUSE");
	return 0;
}

[Stilet]

Предлагаю вариант попроще

{
	int a[15]={7,3,8,8,1,0,2,7,4,4,4,5,2,6,5};
	//             2     5       9        14
	int sum=0,smax=0,q=1,w=2;
	for(int i=0;i<4;i++){
		sum=a[0]+a[q]+a[w];
		printf("\n%d+%d+%d=%d",a[0],a[q],a[w],sum);
		smax=(sum<smax)?smax:sum;
		q+=(i+2);
		w+=(i+3);

	}
	printf("\n%d",smax);
	getchar();
	return 0;
}

[sir.andrey]

Вы не понимаете условие!!!
Вот приведу пример!!!
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Ответ: 30
7 3 8 7 5

        7
       / \
     3   8
    / \  / \
   3   4   5

Надо придумать алгоритм, который просчитывает абсолютно все
способы!!!