0039-数字三角形

问题描述

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

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。注意:路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。

输入

有多组输入数据。
输入的第一行是一个整数 N (1 < N <= 100),给出三角形的行数。下面的 N 行给出数字三角形。数字三角形上的数的范围都在 0 和 100 之间。

输出

输出为单独的一行，这一行中是一个整数，该整数为数字三角形的最大和。

输入样列

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

输出样例

30

算法实现

using System;

namespace Questions{
    class Program{
        public static void Main(string[] args){
            while (true)
            {
                int n = int.Parse(Console.ReadLine());
                if (n == 0)
                    break;
                int[,] result = new int[n, n];
                for (int i = 0; i < n; i++)
                {
                    string input = Console.ReadLine();
                    string[] data = input.Split(' ');
                    for (int j = 0; j <= i; j++)
                    {
                        result[i, j] = int.Parse(data[j]);
                    }
                }

                for (int i = n - 2; i >= 0; i--)
                {
                    for (int j = 0; j <= i; j++)
                    {
                        if (result[i + 1, j] > result[i + 1, j + 1])
                            result[i, j] += result[i + 1, j];
                        else
                            result[i, j] += result[i + 1, j + 1];
                    }
                }
                Console.WriteLine(result[0, 0]);
            }
            Console.ReadKey();
        }
    }
}