Can the Hamiltonian path problem be solved by dynamic programming in $O(2^n n)$ time? Let G(V,E) be the graph and V = {$V_1$,$V_2$,....,$V_n$}. A dynamic programming approach solves the Hamiltonian path problem in $O(2^n n^3)$ time.

We can have a matrix :
dp[s][i][j] : which computes for any subset (say s) of V whether there exists a hamiltonian path starting from vertex $V_i$ and ends at vertex $V_j$ if s includes $V_i$ and $V_j$.

Can we have only dp[s][i] and say whether there exists a hamiltonian path ending at vertex $V_i$ there by solving it in $O(2^n n^2)$ time. Can it be improved furthur?
Yes, the problem can be solved in $O^*(1.657^n)$ time using algebraic methods. See the FOCS paper of Björklund [1].



[1] Björklund, Andreas. "Determinant sums for undirected Hamiltonicity." Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. IEEE, 2010.