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]