Sequence Alignment of two Strings
One general way to speed up dynamic algorithms is the "Method of Four Russians" - \$O(\frac{n^2}{\log n})\$. But to implement this method you should use limited alphabet (not like numbers in your implementation).

Although theoretically this method looks awesome, practically the size of a lookup table is growing fast (\$O(3^{2t} \cdot \left|A \right| \cdot t)\$, where \$\left|A \right|\$ is the size of an alphabet, and \$t\$ is a block size). For example, in the case of DNA (4 letters alphabet) it can fit to the modern cash memory just in the case of \$t\$ equals to 3 (\$\sim0.1MB\$) or 4 (\$\sim10MB\$).

Another way to optimize the pairwise alignment is to take advantage of an extended instruction set of modern CPUs (SIMD extension). Up to now there are several such implementations of the Smith-Waterman algorithm (1 or 2).