Как распечатать путь, пройденный в этом DP?

Question

Я не могу распечатать пройденный путь с помощью DP. Я получаю правильную стоимость кратчайшего пути, но не могу распечатать путь, по которому проходит кратчайший путь.

https://www.geeksforgeeks.org/min-cost-path-dp-6/

Answer 1

Вы не указали, на каком языке, но вот код Java для печати выбранного шага на каждом этапе. Лог c должен быть одинаковым для всех языков:

static int minCost(int cost[][], int m, int n) 
{ 
    if (n < 0 || m < 0) 
        return Integer.MAX_VALUE; 
    else if (m == 0 && n == 0) 
        return cost[m][n]; 
    else {
        int topleft = minCost(cost, m-1, n-1);
        int top = minCost(cost, m-1, n);
        int left = minCost(cost, m, n-1);
        int min = min(topleft, top, left);
        switch (min) {
             case topleft:
                 System.out.println(String.format("(%d, %d)", m-1, n-1));
                 break;
             case top:
                 System.out.println(String.format("(%d, %d)", m-1, n));
                 break;
             case left:
                 System.out.println(String.format("(%d, %d)", m, n-1));
                 break;
        }
        return cost[m][n] + min;
    }
}