Пусть dp[i][j] - количество различных маршрутов из левого верхнего угла в ячейку (i,j).
Попасть в ячейку(i,j) мы можем из ячеек (i-2,j-1) или из (i-1,j-2),исходя из условия задачи.Поэтому dp[i][j]=dp[i-2][j-1]+dp[i-1][j-2]. Разумеется,что в левом верхнем углу конь сможет побывать только однажды!