| 209 | } |
| 210 | |
| 211 | public static int countDP(String exp, boolean result, int start, int end, HashMap<String, Integer> cache) { |
| 212 | String key = "" + result + start + end; |
| 213 | if (cache.containsKey(key)) { |
| 214 | return cache.get(key); |
| 215 | } |
| 216 | if (start == end) { |
| 217 | if (exp.charAt(start) == '1' && result == true) { |
| 218 | return 1; |
| 219 | } else if (exp.charAt(start) == '0' && result == false) { |
| 220 | return 1; |
| 221 | } |
| 222 | return 0; |
| 223 | } |
| 224 | int count = 0; |
| 225 | if (result) { |
| 226 | for (int i = start + 1; i <= end; i += 2) { |
| 227 | char op = exp.charAt(i); |
| 228 | if (op == '&') { |
| 229 | count += countDP(exp, true, start, i - 1, cache) * countDP(exp, true, i + 1, end, cache); |
| 230 | } else if (op == '|') { |
| 231 | count += countDP(exp, true, start, i - 1, cache) * countDP(exp, false, i + 1, end, cache); |
| 232 | count += countDP(exp, false, start, i - 1, cache) * countDP(exp, true, i + 1, end, cache); |
| 233 | count += countDP(exp, true, start, i - 1, cache) * countDP(exp, true, i + 1, end, cache); |
| 234 | } else if (op == '^') { |
| 235 | count += countDP(exp, true, start, i - 1, cache) * countDP(exp, false, i + 1, end, cache); |
| 236 | count += countDP(exp, false, start, i - 1, cache) * countDP(exp, true, i + 1, end, cache); |
| 237 | } |
| 238 | } |
| 239 | } else { |
| 240 | for (int i = start + 1; i <= end; i += 2) { |
| 241 | char op = exp.charAt(i); |
| 242 | if (op == '&') { |
| 243 | count += countDP(exp, false, start, i - 1, cache) * countDP(exp, true, i + 1, end, cache); |
| 244 | count += countDP(exp, true, start, i - 1, cache) * countDP(exp, false, i + 1, end, cache); |
| 245 | count += countDP(exp, false, start, i - 1, cache) * countDP(exp, false, i + 1, end, cache); |
| 246 | } else if (op == '|') { |
| 247 | count += countDP(exp, false, start, i - 1, cache) * countDP(exp, false, i + 1, end, cache); |
| 248 | } else if (op == '^') { |
| 249 | count += countDP(exp, true, start, i - 1, cache) * countDP(exp, true, i + 1, end, cache); |
| 250 | count += countDP(exp, false, start, i - 1, cache) * countDP(exp, false, i + 1, end, cache); |
| 251 | } |
| 252 | } |
| 253 | } |
| 254 | cache.put(key, count); |
| 255 | return count; |
| 256 | } |
| 257 | |
| 258 | public static int total(int n) { |
| 259 | // Function to return (2n) ! / ((n+1)! * n!) |