Complejidad temporal de DFS en la trayectoria más larga creciente en una matriz.

Me encontré con un problema para encontrar el camino más largo creciente en una matriz. La solución de fuerza bruta para esto es bastante directa:

public class Solution {

  private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  private int m, n;

  public int longestIncreasingPath(int[][] matrix) {
      if (matrix.length == 0) return 0;
      m = matrix.length;
      n = matrix[0].length;
      int ans = 0;
      for (int i = 0; i < m; ++i)
          for (int j = 0; j < n; ++j)
              ans = Math.max(ans, dfs(matrix, i, j));
      return ans;
  }

  private int dfs(int[][] matrix, int i, int j) {
      int ans = 0;
      for (int[] d : dirs) {
          int x = i + d[0], y = j + d[1];
          if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
              ans = Math.max(ans, dfs(matrix, x, y));
      }
      return ++ans;
  }
}

Y la complejidad temporal para esto se da como O(2^(m+n)) donde m es el número de filas, y n es el número de columnas en la matriz.

Estoy teniendo dificultades para entender esto. El primer bucle for anidado es O(mn), lo cual está bien. Ahora cada celda se trata como una raíz y se realiza un DFS en ella. Sin embargo, la complejidad temporal para un DFS es O(V + E), y aquí V = mn y E = 4 * mn, por lo que cada dfs debería ser O(mn), por lo que la complejidad temporal total debería ser O(m^2.n^2), ¿verdad?

Nota: Soy consciente de que esta no es una solución óptima y que se puede memoizar, sin embargo, mi pregunta es sobre entender la complejidad temporal de este método de fuerza bruta.