I am doing this problem: CSES - Empty String

I know this is a range DP, and dp[i][j] is the number of ways to empty the range from i to j.

I read this solution here: what is the init() doing? What is ch[][] doing?

I am doing this problem: CSES - Empty String

I know this is a range DP, and dp[i][j] is the number of ways to empty the range from i to j.

I read this solution here: what is the init() doing? What is ch[][] doing?

choose function (`ch[i][j]`

= i\choose j)

Why do we need to do combination in this problem? I am really confused.

`dp[i][j]`

is the number of ways to empty the substring `[i, j]`

to calculate `dp[i][j]`

loop through all middle points, `k`

(`i < k < j`

) such that `s[i] == s[k]`

then, if we choose to remove `s[i]`

and `s[k]`

, then we must remove `dp[i + 1][k - 1]`

first (for `s[i]`

and `s[k]`

to be adjacent)

we also need to remove `[k + 1, j]`

for the substring `[i, j]`

to be removed (which is `dp[k + 1][j]`

).

since we can remove the substring `[i + 1, k - 1]`

and `[k + 1, j]`

in **any** order, we also multiply it by `choose[(j - i - 1) / 2][(k - i + 1) / 2]`

(notice that we divide by two because we remove the letters in pairs)

thus our transition would be `dp[i][j] += dp[i + 1][k - 1] * dp[k + 1][j] * choose[(j - i - 1) / 2][(k - i + 1) / 2]`

such that `s[i] == s[k]`