Как я могу добавить что-то из проблемы рекурсии Java при поиске путей?

Question

Я делаю Java программу, в которой она считает количество путей. Я хочу, чтобы это было только go вверх (север) и вправо (восток). Я также хочу, чтобы он выводил пройденные пути. Что я могу сделать?

import java.io.*;

public class PathsRecursion {
    public static int countPaths(int n, int e) {
        int dp[][] = new int[n + 1][e + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;

        }
        for (int i = 0; i <= e; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= n; i++)
        for (int j = 1; j <= e; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
        return dp[n][e];
    }
    public static void main(String[] args) {
        int n = 1, e = 3;
        System.out.println("Number of Paths: " + countPaths(n, e));
    }
}

Answer 1

Вы добавили дополнительную строку и столбец в свой массив dp. Это должен быть массив n на e, а не n + 1 на e + 1 массив.

import java.io.*;

public class PathsRecursion {
    public static int countPaths(int n, int e) {
        int dp[][] = new int[n][e];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;

        }
        for (int i = 0; i <= e; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= n; i++)
        for (int j = 1; j <= e; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
        return dp[n - 1][e - 1];
    }
    public static void main(String[] args) {
        int n = 1, e = 3;
        System.out.println("Number of Paths: " + countPaths(n, e));
    }
}