Word Problem over Finite Groupoids
This word problem over groupoid is a nice example to show the essence of dynamic programming, the recognition of the subproblems. In other words, how can we define the table or the multi-dimensional array that we should fill?
In general, the subproblems should represent the computations that will be repeated many times in a brute-force algorithm. The subproblems should be refined enough so that we can solve the larger subproblems from the solutions of the smaller subproblems. Please take a moment to appreciate how the subproblems are defined below.
Compute $dp[i][j]$, the set of all possible values of $x_{i}x_{i+1}\cdots x_j$, where $1\le i\le j\le n$.
The goal element $a$ is a possible value of $x$ if and only if $dp[0][n]$ contains $a$.
How to compute $dp[i][j]$?
The base case, $dp[i][i]$ is the set of a single element, $x_i$.
How about the case when $j\ge i+1$? Note a parenthesization of $x_ix_{i+1}\cdots x_j$ means to parenthesize it into two parts, $(x_i\cdots x_t)(x_{t+1}\cdots x_j)$ for some $i\le t\lt j$, followed by a parenthesization of the front part $x_i\cdots x_t$ and a parenthesization of the behind part, $x_{t+1}\cdots x_j$. So $dp[i][j]$ contains all products of the form $f\cdot b$, where $f$ is a possible value of the front part and $b$ is a possible of the behind part. Note both the front part and behind part are shorter than the whole, $x_ix_{i+1}\cdots x_j$.
In other word, in order to compute $dp[i][j]$, we can iterate $f$ through all elements in $dp[i][t]$ and $b$ through all elements in $dp[t+1][j]$, adding the product $f\cdot b$ to $dp[i][j]$.
There are $n(n-1)/2$ choices for $i$ and $j$. There are at most $n$ choices for $t$. There are at most $k$ choices for $f$. There are at most $k$ choices for $b$. Depending on the implementation, it takes $O(k\cdot k\cdot k)$ or much less time to compute product $f\cdot b$ and add it to a set of at most $k$ elements. Hence the time-complexity of the algorithm is polynomial in $n$ and $k$.