Understanding the top-down solution to the palindrome partitioning problem

To solve the palindrome partitioning problem using a top-down dynamic programming approach, we translate the recurrence relation into recursive functions and use memoization tables to store results of subproblems that have already been solved.

The top-down solution

As with any top-down solution, there are recursive functions that solve subproblems and a calling function that initializes the required data structures and triggers the computation. The recurrence relation for the palindrome partitioning problem has two parts where one relies on the result of the other, and so we define two recursive functions that work together to solve the problem.

Why do we need two recursive functions instead of one?

The palindrome partitioning problem requires answering two distinct questions at each state:

Is this substring a palindrome?
A yes/no question handled by isPalindromeWhat is the minimum number of cuts needed to partition this substring into palindromic pieces?
A numeric question handled by minCuts.

These are separated into two functions because combining them into one would force every minCuts call to redo the palindrome check from scratch, losing the benefit of memoization on the simpler sub-question.

The isPalindrome function

The function isPalindrome() takes as input a left index i, a right index j, a reference to the string s, and a reference to the 2D memoization array palindromeMemo. The function returns whether the substring s[i...j] is a palindrome.

Create a function isPalindrome to return if the substring s[i...j] is palindrome or not.

The palindromeMemo array has dimensions n × n and is initialized with -1 in the calling function, where -1 indicates that the state has not yet been computed. A value of 0 represents false, and 1 represents true.