Problem $2.$ Word Partitioning $(32$ points$)$

Given and array $A[1$dotsn$]$ of characters, we say A can be word partitioned if it can be

decomposed into disjoint substrings, where each substring is an English word. For example,

the string ARTISTOIL can be word partitioned as ARTIST $-$ OIL, or as ART $-$ IS $-$ TOIL.

You are given a subroutine IsWord$(i,j),$ which for any $ij$ in constant time returns

True if $A[idotsj]$ is a word, and False otherwise. Using this subroutine, give an $O(n^2)$ time

algorithm to compute the number of distinct ways in which A can be word partitioned.