Сколько способов вернуться в исходную точку через n шагов

Задача: Вы стартуете из точки 0 в массиве длины h. На каждом шаге вы можете перейти влево (но только не в точке 0) или вправо. Из точки 0- можно перейти только вправо. Остаться на месте - это тоже шаг. Сколько способов есть обнаружить себя в точке 0 через  n шагов (включая стояние на месте)?

Исходная формулировка:

Problem: You start at index 0 in an array with length 'h'. At each step, you can move to the left, move to the right, or stay in the same place. (Note! Stay in the same place also takes one step). How many possible ways are you still at index 0 after you have walked 'n' step?

Источник задачи: https://leetcode.com/discuss/interview-question/416381/google-phone-interview-question-dp

Компилируемый код с решением:

public static int solve(int h, int n) {
        int d[][] = new int[n+1][h];
        for (int i = 0; i<h; i++) {
            d[0][i]=0;
        }
        // first step
        d[1][0]=1;
        d[1][1]=1;
        // other steps
        for (int step=2; step<n+1; step++){
            for (int position = 0; position<h; position++) {
                int a = 0; int b=0;
                if (position-1 >= 0) a = d[step-1][position-1];
                if (position+1 <h) b = d[step-1][position+1];
                d[step][position] = a + d[step-1][position] + b;
            }
        }
        return d[n][0];
    }

Объяснение:
Каждая ячейка d[s][x] содержит колинество возхможных способов очутиться в точки x после  s шагов.

За 1 шаг мы можем остаться в точке 0 или перейти в точку 1. Другие точки недостижимы.

На шаге 2 мы можем

• очутиться в точке 0, оставаясь в  ней, или вернувшись из точки 1;
• продолжать стоять в точке 1 или перейти из точки 0;
• из 1 перейти в 2.

Обобщим: перейти в точку position на шаге step мы можем из точек position-1, position, position+1, учитывая границы (начало и конец массива). Но в эти точки мы попали соответственно a, b, c способами за step-1 шагов. Поэтому суммируем способы достижения этих точек, чтобы оказаться в точке position на шаге step.

Элегантное рекурсивное решение было предложено в коменариях задачи (оно и привело меня к решению):

int solve(int pos, int i, int n, int h) {
        if (i == n && pos == 0) return 1;
        if (i == n) return 0;
        if (pos >= h || pos < 0) return 0;

        int cnt = 0;

        cnt += solve(pos - 1, i + 1, n, h);
        cnt += solve(pos, i + 1, n, h);
        cnt += solve(pos + 1, i + 1, n, h);
   
        return cnt;
    }

В рекурсивном решении есть много шагов, которые считаются многократно, например solve(1, 3, 3, 3) считается аж 5 раз! (Распишите просто формулу, для n=3). Это означает, что оказаться в точке 1 через 3 шага, если n=3 и h=3 можно 5 раз.

В то же время d[3][1] подсчитывается толлько 1 раз и равно 5!