\(dp[i][j] = \) (\(s(i, j); s\) の \(i\) 文字目から \(j - 1\) 文字目までの文字列，に対する答え) とします（半開区間であることに注意してください）．はじめ，これらは全て \(0\) で初期化されています．この DP を，文字列の長さの小さい順に求めていきます．

この文字列の両端の i を用いた操作を行ったか否かに応じて，

• この文字列の両端の i を用いた操作を行った場合
  • 操作で用いた w の位置を全探索します．操作で用いた w が \(k\) 文字目であるとき，\(dp[i][j] = \max(dp[i ][j], dp[i + 1][k] + dp[k + 1][j])\) と遷移します．ただし，この遷移が行えるのは \(s(i + 1, k)\) および \(s(k + 1, j)\) を操作によって空文字列にできる場合に限ります．\(dp[i + 1][k], dp[k + 1][j]\) およびそれら部分文字列の長さの値から，遷移が可能かの判断が必要です．
• そうでない場合
  • \(2\) つの区間に対する答えをマージします．\(dp[i][j] = \max_{i \leq k \leq j} (dp[i][j], dp[i][k] + dp[k][j[)\) と遷移します．

\(dp[0][N]\) が答えです．状態数が \(O(N^2)\)，遷移が \(O(N)\) なので全体での計算量は \(O(N^3)\) です．