MoveDownRightSum Algorithm

using System;
using System.Collections.Generic;
using System.Data;
using System.Linq;

namespace MoveDownRightSum
{
    class Program
    {
        static void Main(string[] args)
        {
            int[ , ] cells =
            {
                {2, 6, 1, 8, 9, 4, 2},                           //You are given a matrix of numbers
                {1, 8, 0, 3, 5, 6, 7},                           //Find the largest sum of cells, starting from the top left corner
                {3, 4, 8, 7, 2, 1, 8},                           //Ending at the bottom right corner, going down or right each step.
                {0, 9, 2, 8, 1, 7, 9},                           //Задача от динамично оптимиране.
                {2, 7, 1, 9, 7, 8, 2},
                {4, 5, 6, 1, 2, 5, 6},
                {9, 3, 5, 2, 8, 1, 9},
                {2, 3, 4, 1, 7, 2, 8}
            };
             int[,] sums = new int[cells.GetLength(0), cells.GetLength(1)]; //Нова матрица, в която ще запазваме сумите от пътя до съответната клетка.
            sums[0, 0] = cells[0, 0];
            //Сумираме клетките в нулевия ред
            for (int row = 1; row < sums.GetLength(0); row++)
            {
                sums[row, 0] = sums[row - 1, 0] + cells[row, 0];
            }
            //Сумираме клетките  в нулевата колона
            for (int col = 1; col < cells.GetLength(1); col++)
            {
                sums[0, col] = sums[0, col - 1] + cells[0, col];
            }
            //Попълваме остатъка от матрицата със сумите
            for (int row = 1; row < sums.GetLength(0); row++)
            {
                for (int col = 1; col < sums.GetLength(1); col++)
                {
                    //Взимаме по-голямата сума от тази отгоре и тази отляво+числото от матрицата за текущата клетка=сумата, която ще държи текущата клетка
                    sums[row, col] = Math.Max(sums[row - 1, col], sums[row, col - 1]) + cells[row, col];
                }
            }
            var path = ReconstructPath(sums); //Погледнете метода най-отдолу
            //Печат на попълнената матрица със суми(за онагледяване)
            for (int row = 0; row < sums.GetLength(0); row++)
            {
                for (int col = 0; col < sums.GetLength(1); col++)
                {
                    if (path.Contains(new Tuple<int, int>(row, col))) //Ако хешсетът съдържа съответната клетка, оцветяваме в зелено
                    {
                        Console.ForegroundColor = ConsoleColor.Green;
                    }
                    Console.Write("{0, 3}", sums[row, col]);
                    Console.ForegroundColor = ConsoleColor.White; // Връщаме цветът на бяло
                }
                Console.WriteLine();
            }
            Console.WriteLine();
            //Печат на самата матрица
            for (int row = 0; row < sums.GetLength(0); row++)
            {
                for (int col = 0; col < sums.GetLength(1); col++)
                {
                    if (path.Contains(new Tuple<int, int>(row, col)))
                    {
                        Console.ForegroundColor = ConsoleColor.Green;
                    }
                    Console.Write("{0, 3}", cells[row, col]);
                    Console.ForegroundColor = ConsoleColor.White;
                }
                Console.WriteLine();
            }
        }
        //Изграждаме пътя в обратен ред, от последната сума проверявайки накъде е по-голяма сумата
        //(тоест подходящия път по който сме стигнали)  в хешсет.
        private static HashSet<Tuple<int, int>> ReconstructPath(int[,] sums)
        {
            var path = new HashSet<Tuple<int, int>>();
            int r = sums.GetLength(0) - 1;
            int c = sums.GetLength(1) - 1;
            path.Add(new Tuple<int, int>(r, c)); // Добавяме последната сума в хешсета
            while (r > 0 && c > 0)
            {
                if (sums[r - 1, c] > sums[r, c - 1])  //Ако сумата отляво е по-голяма, добавяме я в пътя
                {
                    path.Add(new Tuple<int, int>(r - 1, c));
                    r--;
                }
                else                                                        //В противен случай добавяме сумата отгоре
                {
                    path.Add(new Tuple<int, int>(r, c - 1));
                    c--;
                }
            }
            //Понеже вече сме стигнали или 0-та колона или 0-я ред, но може би не и края на пътя, попълваме остатъка(това което не е стигнало 0)
            while (r > 0)
            {
                path.Add(new Tuple<int, int>(r - 1, c));
                r--;
            }
            while (c > 0)
            {
                path.Add(new Tuple<int, int>(r, c - 1));
                c--;
            }
            return path;
        }
    }
}