Оптимизация алгоритмической задачи про ход коня

Question

Дана прямоугольная доска размером NхM. В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. В данной задаче конь может перемещаться на две клетки вниз и одну клетку вправо или на одну клетку вниз и две клетки вправо.

Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.

N и M находятся в пределах от 1 до 50. Ограничение по времени работы - 1000 мс, по памяти - 64 мб.

Пример 1: Вход: N=1 M=1 Выход: 0

Пример 2: Вход: N=3 M=2 Выход: 1

Пример 3: Вход: N=31 M=34 Выход: 293930

Я написал следующее решение:

public class Main {
    private static int counter = 0;
    public static void main(String[] args) {
        int n = 50; // input N
        int m = 50; // input M
        walk(0, 0, n-1, m-1);
        System.out.println(counter); // Output result
    }

    private static void walk(int i, int j, int n, int m) {
        if (i < n && j < m) {
            walk(i + 2, j + 1, n, m);
            walk(i + 1, j + 2, n, m);
        } else if (i == n && j == m) {
            counter += 1;
        }
    }
}

Однако с этим решением есть проблема с тем, что при больших значениях входных параметров время работы алгоритма не укладывается в 1000мс (пример, N=50, M=50). Какие есть варианты оптимизации?

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

Answer 1

Немного разобравшись в решении, которое привел @Harry и подправив код, получился следующий рабочий вариант:

public class Main {
    private static int counter = 0;
    public static void main(String[] args) {
        int n = 50; // input N
        int m = 50; // input M
        int dp[][] = new int[n+1][m+1];
        dp[1][1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                dp[i][j] = dp[i-1][j-2] + dp[i-2][j-1];
            }
        }
        System.out.println(String.valueOf(dp[n][m])); // Output result
    }
}

Answer 2

TODO: объяснить что происходит.

import java.util.Scanner;

public class Temp {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int m = s.nextInt();
        int k = n + m - 2;
        if (k % 3 == 0) {
            int q = k / 3;
            System.out.println(cnk(q, (n - 1) - q));
        } else {
            System.out.println(0);
        }
    }

    private static int cnk(int n, int k) {
        if (k < 0 || n < k) {
            return 0;
        }
        int p = 1;
        for (int i = 1; i <= n - k; ++i) {
            p = p * (i + k) / i;
        }
        return p;
    }
}

БЛОГ НА HUSL

Оптимизация алгоритмической задачи про ход коня

Ответы (2 шт):