 # CSES Empty String

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]`