How to create a cost matrix?

There are a lot of different packages and therefore a lot of possibilities to do this. Here is one with the matrix library of the TikZ package.

Update 1 : problem on a arrow

The first code reverses an arrow and I haven't figured out why yet. To correct this, the code becomes heavier.

\documentclass[border=5mm,tikz]{standalone}
\usetikzlibrary{matrix,arrows.meta}
\begin{document}
\begin{tikzpicture}[>={Stealth[length=4pt]}]
\matrix (cost)[matrix of nodes,nodes in empty cells]
{ & & B & A & B & A & A & A \\
  & 0 & 1 & 2 & 3 & 4 & 5 & 6\\
A & 1 & 2 & 1 & 2 & 3 & 4 & 5\\
B & 2 & 1 & 2 & 1 & 2 & 3 & 4 \\
A & 3 & 2 & 1 & 2 & 1 & 2 & 3\\
B & 4 & 3 & 2 & 1 & 2 & 3 & 4\\
B & 5 & 4 & 3 & 2 & 3 & 4 & 5\\
B & 6 & 5 & 4 & 3 & 4 & 5 & 6\\  
};
\draw (cost-1-8.south east) -| (cost-8-1.south east)-| cycle;
\draw (cost-2-8.south east) -| (cost-8-2.south east);
\foreach \x/\y [remember =\x as \lastx (initially 8),remember=\y as \lasty (initially 8)] in {7/7,6/6}{
 \draw[->,shorten <=-3pt,shorten >=-3pt](cost-\lastx-\lasty)--(cost-\x-\y);
 }
 
 \draw[<-,shorten <=-3pt,shorten >=-3pt] (cost-6-6)--(cost-5-6);
\foreach \x/\y [remember =\x as \lastx (initially 5),remember=\y as \lasty (initially 6)] in {4/5,3/4,2/3,2/2}{
 \draw[->,shorten <=-3pt,shorten >=-3pt](cost-\lastx-\lasty)--(cost-\x-\y);
 }
\end{tikzpicture}

\end{document}

\documentclass[border=5mm,tikz]{standalone}
\usetikzlibrary{matrix,arrows.meta}
\begin{document}
\begin{tikzpicture}[>={Stealth[length=4pt]}]
\matrix (cost)[matrix of nodes,nodes in empty cells]
{ & & B & A & B & A & A & A \\
  & 0 & 1 & 2 & 3 & 4 & 5 & 6\\
A & 1 & 2 & 1 & 2 & 3 & 4 & 5\\
B & 2 & 1 & 2 & 1 & 2 & 3 & 4 \\
A & 3 & 2 & 1 & 2 & 1 & 2 & 3\\
B & 4 & 3 & 2 & 1 & 2 & 3 & 4\\
B & 5 & 4 & 3 & 2 & 3 & 4 & 5\\
B & 6 & 5 & 4 & 3 & 4 & 5 & 6\\  
};
\draw (cost-1-8.south east) -| (cost-8-1.south east)-| cycle;
\draw (cost-2-8.south east) -| (cost-8-2.south east);
\foreach \x/\y [remember =\x as \lastx (initially 8),remember=\y as \lasty (initially 8)] in {7/7,6/6,5/6,4/5,3/4,2/3,2/2}{
 \draw[->,shorten <=-3pt,shorten >=-3pt](cost-\lastx-\lasty)--(cost-\x-\y);
 }

\end{tikzpicture}

\end{document}

I have edited this answer because, since version 5.5 (2020-10-20), one must no longer write \omit\CodeAfter here (now, \CodeAfter works in all circonstancies).

---

With nicematrix:

\documentclass{article}
\usepackage{nicematrix}
\usepackage{tikz}
\begin{document}

\renewcommand{\arraystretch}{1.2}

\begin{NiceTabular}{|ccccccc|}[first-row,first-col]
  &   & B & A & B & A & A & A \\
\hline
  & 0 & 1 & 2 & 3 & 4 & 5 & 6\\
A & 1 & 2 & 1 & 2 & 3 & 4 & 5\\
B & 2 & 1 & 2 & 1 & 2 & 3 & 4\\
A & 3 & 2 & 1 & 2 & 1 & 2 & 3\\
B & 4 & 3 & 2 & 1 & 2 & 3 & 4\\
B & 5 & 4 & 3 & 2 & 3 & 4 & 5\\
B & 6 & 5 & 4 & 3 & 4 & 5 & 6\\  
\hline
\CodeAfter
\begin{tikzpicture}
\draw (row-8-|col-2) -- (row-2-|col-2) -- (row-2-|col-8) ;
\begin{scope}[->,shorten < = 1pt, shorten > = 1pt]
\draw (1-2) -- (1-1) ;
\draw (2-3) -- (1-2) ;
\draw (3-4) -- (2-3) ;
\draw (4-5) -- (3-4) ;
\draw (5-5) -- (4-5) ;
\draw (6-6) -- (5-5) ;
\draw (7-7) -- (6-6) ;
\end{scope}
\end{tikzpicture}
\end{NiceTabular}

\end{document}

A solution for both images, based on ordinary tabulars and the help of pstricks for the connections:

\documentclass[table]{article}
\usepackage{array}
\usepackage{tabularx} 
\usepackage{xcolor}
\usepackage{pst-node, multido} 

\begin{document}

\sffamily\setlength{\extrarowheight}{3pt}
\begin{tabularx}{\linewidth}{XX}
 { \begin{tabular}[t]{c|c|*{6}{c}|}
\multicolumn{3}{c}{}B & A & B & A & A & \multicolumn{1}{c}{A} \\
\cline{2-8}
 & \multicolumn{1}{c}{\rnode{8}{0}} & \rnode{7}{1} & 2 & 3 & 4 & 5 & 6 \\
 \cline{3-8}
 A & 1 & 2 & \rnode{6}{1} & 2 & 3 & 4 & 5 \\[2pt]
 B & 2 & 1 & 2 & \rnode{5}{1} & 2 & 3 & 4 \\[2pt]
 A & 3 & 2 & 1 & 2 & \rnode{4}{1} & 2 & 3 \\[2pt]
 B & 4 & 3 & 2 & 1 & \rnode{3}{2} & 3 & 4 \\[2pt]
 B & 5 & 4 & 3 & 2 & 3 & \rnode{2}{4} & 5 \\[2pt]
 B & 6 & 5 & 4 & 3 & 4 & 5 & \rnode{1}{6} \\
\cline{2-8}
\end{tabular}
\psset{arrows=->, arrowinset=0.12,linejoin=1, nodesep=1pt}
\multido{\is=1+1,\it=2+1}{7}{\ncline{\is}{\it}}}
 &
{\Large Trace\bigskip}\newline
{\setlength{\tabcolsep}{8pt}\begin{tabular}[t]{*{6}{c}}
  A & B & A & B & B & B \\[-1ex]
\pnode{U1} & \pnode{U2} & \pnode{U3} & & \pnode{U4} & \pnode{U5}\\[1em]
 & \pnode{D1} & \pnode{D2} & \pnode{D3} & \pnode{D4} & \pnode{D5}\\
B & A & B & A & A & A
\end{tabular}}
\multido{\i=1+1}{5}{\ncline{D\i}{U\i}}
\end{tabularx}

\end{document}