# Dinamikus programozás - MINIMÁLIS KÖLTSÉGŰ ÚT

sor = 3
oszlop = 3

def mK(koltseg, m, n):
    temp=[[0 for x in range(oszlop)] for x in range(sor)]

    temp[0][0] = koltseg[0][0]

    #temp mátrix első oszlopának inicializálása 
    for i in range(1, m+1):
        temp[i][0] = temp[i-1][0] + koltseg[i][0]

    #temp mátrix első sorának inicializálása 
    for j in range(1, n+1):
        temp[0][j] = temp[0][j-1] + koltseg[0][j]

    #Maradék részek feltöltése (itt a rekurzív lépés)
    for i in range(1, m+1):
        for j in range(1, n+1):
            temp[i][j] = min(temp[i-1][j-1], temp[i-1][j], temp[i][j-1]) + koltseg[i][j]
            print('TEMP mátrix felépítése (aktuális állapot):\n', temp)
            input('Enter és folytat...')

    return temp[m][n]


koltseg=[[1, 2, 3],
         [4, 8, 2],
	 [1, 5, 3]]
print('A költség mátrix:\n', koltseg)
print('A minimális költségű út költsége:\n', mK(koltseg, 2, 2))