Number of Ways to Partition a String into a Palindromes | Dynamic Programming

Prereq: Palindrome Counting

The problem is exactly the same as in Palindrome Partitioning except instead of outputting every possible palindrome, we instead ask you to simply output the number of possible partitions. The string size can be up to 2000 characters in length. The number will be guaranteed to fit into an int.

Examples

Example 1:

Input: aab

Output: 2

Try it yourself