1    # Dinamikus programozás - MINIMÁLIS KÖLTSÉGŰ ÚT
2    
3    sor = 3
4    oszlop = 3
5    
6    def mK(koltseg, m, n):
7        temp=[[0 for x in range(oszlop)] for x in range(sor)]
8    
9        temp[0][0] = koltseg[0][0]
10   
11       #temp mátrix első oszlopának inicializálása 
12       for i in range(1, m+1):
13           temp[i][0] = temp[i-1][0] + koltseg[i][0]
14   
15       #temp mátrix első sorának inicializálása 
16       for j in range(1, n+1):
17           temp[0][j] = temp[0][j-1] + koltseg[0][j]
18   
19       #Maradék részek feltöltése (itt a rekurzív lépés)
20       for i in range(1, m+1):
21           for j in range(1, n+1):
22               temp[i][j] = min(temp[i-1][j-1], temp[i-1][j], temp[i][j-1]) + koltseg[i][j]
23               print('TEMP mátrix felépítése (aktuális állapot):\n', temp)
24               input('Enter és folytat...')
25   
26       return temp[m][n]
27   
28   
29   koltseg=[[1, 2, 3],
30            [4, 8, 2],
31   	 [1, 5, 3]]
32   print('A költség mátrix:\n', koltseg)
33   print('A minimális költségű út költsége:\n', mK(koltseg, 2, 2))
34   
35