Ścieżka

using System;
using System.Collections.Generic;
class Program
{
    // wynik [0,0] = 0
    // wynik [0,j] = w[0, j-1] + p[0, j-1]
    // wynik [i,0] = w[i-1 ,0] + d[i-1, 0]
    // wynik [i,j] = max(w[i, j-1] + p[i, j-1],  w[i-1 ,j] + d[i-1, j])
    static int Nagroda(int[,] p, int[,] d,int n,int m,int[,]kroki)
    {
        int[,] wynik = new int[n + 1, m+1];
        wynik[0, 0] = 0;
        for (int i = 1; i < n+1; i++)
        {
            wynik[i,0]=wynik[i-1,0]+d[i-1,0];
            kroki[i, 0] = 1;//down
        }

        for (int j = 1; j < m+1; j++)
        {
            wynik[0, j] = wynik[0, j - 1] + p[0, j - 1];
            kroki[0, j] = 2;//right
        }

        for (int i = 1; i < n+1; i++)
        {
            for (int j = 1; j < m+1; j++)
            {
                //wynik[i, j] = Math.Max(wynik[i, j - 1] + p[i, j - 1], wynik[i - 1, j] + d[i - 1, j]);
                if(wynik[i, j - 1] + p[i, j - 1]>= wynik[i - 1, j] + d[i - 1, j])
                {
                    wynik[i, j] = wynik[i, j - 1] + p[i, j - 1];
                    kroki[i, j] = 2;//right
                }
                else
                {
                    wynik[i, j] = wynik[i - 1, j] + d[i - 1, j];
                    kroki[i, j] = 1;//down
                }
            }
        }
        return wynik[n, m];
    }
    static void ścieżka(int[,]kroki,int n,int m)
    {
        int i = n;
        int j = m;
        Stack<string> s = new Stack<string>();
        while (kroki[i,j]>0)
        {
            if (kroki[i,j]==1)
            {
                s.Push("down");
                i--;
            }
            else
            {
                s.Push("right");
                j--;
            }
        }
        while (s.Count>0)
        {
            Console.WriteLine(s.Pop());
        }
    }
    static void Main(string[] args)
    {
        int n = 4, m = 4;
        int[,] p =
        {
            { 3,2,4,0 },
            { 3,2,4,2 },
            { 0,7,3,4 },
            { 3,3,0,2 },
            { 1,3,2,2 }
        };
        int[,] d =
        {
            { 1,0,2,4,3 },
            { 3,6,5,2,1 },
            { 4,4,5,2,1 },
            { 5,6,8,5,3 }
        };
        int[,] kroki = new int[n + 1, m + 1];
        Console.WriteLine(Nagroda(p,d,n,m,kroki));
        ścieżka(kroki, n, m);
        Console.ReadKey();
    }
}