Путь максимальной суммы Треугольник и получить числа, которые были добавлены С#

"...но я не могу найти способ найти все числа, которые были суммированы"

Вы так близко. Вы храните всю информацию, необходимую для построения пути через пирамиду. list выглядит так после вложенных циклов for. Можете ли вы придумать простой способ обойти list, чтобы найти путь?

1320 
1265 1130 
1171 1061 1082 
1076 1031 986  925  
999  903  960  813  858  
902  890  884  754  775  813  
895  854  805  682  738  694  745  
793  847  796  664  644  668  660  739  
719  775  717  618  585  543  589  631  649  
643  699  630  607  553  522  536  582  554  631  
566  616  512  572  482  466  511  509  525  509  546  
489  552  465  476  454  455  448  453  433  384  491  467  
487  445  462  416  383  406  364  407  400  348  342  444  426  
348  395  372  414  332  347  253  322  328  328  225  260  367  384  
292  220  317  334  293  272  216  251  245  262  204  224  257  312  292  
248  195  145  250  222  172  205  129  190  205  146  135  135  217  256  219  
33   163  120  98   165  124  121  94   75   143  98   129  134  62   118  167  108  
27   2    92   23   8    71   76   84   15   52   92   63   81   10   44   10   69   93   

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

Тем не менее, учитывая, что вы знаете о подходе динамического программирования, описанном на https://www.mathblog.dk/project-euler-18/, надеюсь, вам будет полезно дать некоторое представление о том, как должно выглядеть ваше решение, без фактического написания решения для вас.

Итак, в частности, рассмотрим описанный алгоритм. Суть алгоритма в том, что он решает все подзадачи в нижней части вашего треугольника, складывая (или «сворачивая») результат из нижней строки в следующую строку выше.

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

Это легко сделать, введя новый массив с теми же размерами, что и исходный, но где вместо значений из ввода вы храните в массиве некоторое указание на то, было ли вычислено значение путем суммирования значения слева или справа. в строке ниже (естественно, этому массиву не потребуются какие-либо фактические данные в самой нижней строке, вы можете либо просто игнорировать значения там, либо вы можете сделать массив на одну строку меньше, чем исходный массив данных).

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

С этой информацией вы теперь знаете, какой элемент из второй строки был использован. И массив хлебных крошек сообщает вам, какой элемент из строки ниже этой (третьей строки) был использован. И так далее.

Есть и другие способы спроектировать структуру данных для достижения той же цели. Но все они сводятся к одной и той же основной идее: где-то хранить информацию о том, как была рассчитана каждая сумма, чтобы вы могли воспроизвести ее позже.

Вам не составит труда изменить уже имеющийся код, включить этот дополнительный массив, а затем использовать его позже, чтобы вспомнить пройденный путь.

Наконец, в духе аспекта динамического программирования, я укажу, что если вы строите свою выходную строку по мере продвижения, вам даже не нужен многомерный массив. Вместо этого вы просто начинаете с массива, содержащего строки, который имеет длину, равную предпоследней строке, и где первая строка, хранящаяся в каждом элементе массива, представляет собой просто число, которое было добавлено к текущему элементу в следующем ряду. -последний ряд.

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

И я отмечу, что этот метод «сохранить только одномерный массив» может работать и для промежуточных сумм. т.е. единственный двумерный массив, который вам действительно нужен, это тот, который содержит исходные данные. На каждой итерации вас интересует только самая последняя строка, поэтому вам просто нужен одномерный массив для этой строки.

Другой подход к динамическому программированию заключается в выполнении поиска в глубину, поскольку пирамида представляет собой просто дерево. Это соответствует методу «грубой силы», упомянутому в блоге @peterduniho. Основная идея очень проста: вы проверяете каждый путь от корня (55) до конечных узлов (27, 2 и т. д.).

Я устанавливаю леса, чтобы вы могли двигаться. Вам может показаться, что с таким представлением данных немного проще работать, так как вам не нужно так много думать об индексах и ошибках, отличных друг от друга, и вы можете больше сосредоточиться на том, как решить проблему. Это также упрощает использование функций отладки Visual Studio (например, вы можете поставить точку останова в коде и просмотреть потомков и потомков потомков и т. д.).

Если вы не знакомы с рекурсией, ключевой момент в коде, на который следует обратить внимание, это то, что DepthFirstSearch вызывает сам себя.

(Я думаю, что динамическое программирование - лучший способ решить эту проблему, но я просто публикую это как альтернативу)

    public void Solve()
    {
        string input = 
                                @"55
                                94 48
                               95 30 96
                             77 71 26 67
                            97 13 76 38 45
                          07 36 79 16 37 68
                         48 07 09 18 70 26 06
                       18 72 79 46 59 79 29 90
                      20 76 87 11 32 07 07 49 18
                    27 83 58 35 71 11 25 57 29 85
                   14 64 36 96 27 11 58 56 92 18 55
                 02 90 03 60 48 49 41 46 33 36 47 23
                92 50 48 02 36 59 42 79 72 20 82 77 42
              56 78 38 80 39 75 02 71 66 66 01 03 55 72
             44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
           85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
          06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
        27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93";

        var tree = input.Split('\n')
            .Select(line => line.Trim()
                .Split(' ')
                .Select(s => new Node(int.Parse(s.Trim())))
                .ToArray())
            .ToArray();

        for (var i = 0; i < tree.Length-1; i++)
        {
            for (var j = 0; j < tree[i].Length; j++)
            {
                tree[i][j].Descendants.Add(tree[i + 1][j]);
                tree[i][j].Descendants.Add(tree[i + 1][j+1]);
            }
        }
        var root = tree[0][0];
        int maxSum = 0;
        DepthFirstSearch(tree[0][0],  ImmutableList<Node>.Empty.Add(root), 0, ref maxSum);
    }


    private void DepthFirstSearch(Node root, ImmutableList<Node> path, int runningSum, ref int maxSum)
    {
        CheckBaseCase(root, path, ref maxSum);
        foreach(var node in root.Descendants)
        {
            runningSum += node.Value;
            DepthFirstSearch(node, path.Add(node), runningSum, ref maxSum);
        }
    }

    private void CheckBaseCase(Node root, ImmutableList<Node> path, ref int maxSum)
    {
        // Fill me in!
    }

   [DebuggerDisplay("Value = {Value}, DescendantCount={Descendants.Count}")]
   class Node
   {
       public Node(int value)
       {
           Value = value;
       }
       public int Value{ get; }
       public List<Node> Descendants { get; } = new List<Node>();
   }