возможные пути Короли движутся из нижнего правого в верхний левый угол с максимальной суммой

Question

у нас есть матрица m n. Кинг находится в позиции m n, и он должен достичь позиции 0 * 0. Он может двигаться влево, вверх и по диагонали (слева). на каждом шаге есть определенное значение, и мы должны найти путь с максимальной суммой, чтобы достичь от m * n до 0 * 0.

Example:
D 1 2
2 3 4
1 2 S
Output: S 4 3 2 D as the sum of steps is max (4+3+2) 

Я искал и пробовал несколько решений, но не получил правильный ответ. это терпит неудачу некоторый сценарий. В настоящее время я нахожу все возможные пути и получаю сумму всех доступных путей, а затем нахожу максимальное значение. найдите мой код ниже:

public class KingMarch {
    static List<String> re = new ArrayList<>();
    static List<Integer> result = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        String arr[][] = new String[n][n];
        sc.nextLine();
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                arr[j][k] = sc.next();
            }
            sc.nextLine();
        }
        int len = arr.length;
        recursion(len - 1, len - 1, arr, 0);
        System.out.println("max = " + getMax(result));
    }

    private static void recursion(int i, int j, String[][] arr, int idx) {

        if (i == -1 || j == -1)
            return;

        if (!arr[i][j].equalsIgnoreCase("S") && !arr[i][j].equalsIgnoreCase("D")) {
            re.add(arr[i][j]);
        }

        if (arr[i][j].equalsIgnoreCase("D")) {
            result.add(sum(re));
            printPath(re);
            re.clear();
        }

        recursion(i, j - 1, arr, idx + 1); // left
        recursion(i - 1, j - 1, arr, idx + 1); // diag
        recursion(i - 1, j, arr, idx + 1); // top

    }

    private static void printPath(List<String> re) {
        System.out.println("----NEW---");
        for (String i : re) {
            System.out.print(i + ", ");
        }

    }

    private static int getMax(List<Integer> result) {
        int max = 0;
        for (int i : result) {
            if (i > max)
                max = i;
        }
        return max;
    }

    private static int sum(List<String> re) {
        int sum = 0;
        for (String i : re) {
            sum += Integer.parseInt(i);
        }
        return sum;
    }

}

Я ожидаю, что это даст мне правильный путь с максимальной суммой.