Có thể thấy tổng ~f(s)^2~ chính là số cặp đường đi ~(X, Y)~ sao cho ~s(X) = s(Y)~ (Xâu tạo ra từ đường đi ~X~ giống với xâu tạo ra từ đường đi ~Y~).

Từ đó ta có ý tưởng như sau, gọi ~f(r_1, c_1, r_2, c_2)~ là số cặp đường đi tạo ra xâu giống nhau mà đường đi thứ nhất đang ở ô ~(r_1, c_1)~ và đường đi thứ hai đang ở ô ~(r_2, c_2)~.

Dễ thấy ta có thể đi vào ô ~(r_1, c_1)~ từ ô ~(r_1 - 1, c_1)~ hoặc ~(r_1, c_1 - 1)~. Tương tự có thể đi vào ô ~(r_2, c_2)~ từ ô ~(r_2 - 1, c_2)~ hoặc ~(r_2, c_2 - 1)~. Ta có công thức tính ~f(r_1, c_1, r_2, c_2)~ như sau:

Nếu ~c[r_1][c_1] = c[r_2][c_2]~: ~f(r_1, c_1, r_2, c_2) = f(r_1 - 1, c_1, r_2 - 1, c_2) + f(r_1 - 1, c_1, r_2, c_2 - 1) + f(r_1, c_1 - 1, r_2 - 1, c_2) + f(r_1, c_1 - 1, r_2, c_2 - 1)~

Ngược lại: ~f(r_1, c_1, r_2, c_2) = 0~

Với công thức quy hoạch động như trên ta có thể tính ~f~ với độ phức tạp ~O((m \times n)^2)~

Dễ thấy để hai xâu bằng nhau thì trước hết phải có cùng độ dài nên ta chỉ cần xét các căp ~(r_1, c_1)~ và ~(r_2, c_2)~ mà ~r_1 + c_1 = r_2 + c_2~. Từ đây ta có thể bỏ một chiều của ~f~, ví dụ ta chỉ cần lưu ~f(r_1, c_1, r_2)~ vì có thể tính ~c_2 = r_1 + c_1 - r_2~ . Bằng cách này độ phức tạp giảm xuống còn ~O(m \times n \times min(m, n))~.