Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
Let <code>dp[i]</code> be the minimum number of partitions for the prefix ending at index <code>i + 1</code>.
<code>dp[i]</code> can be calculated as the <code>min(dp[j])</code> over all <code>j</code> such that <code>j < i</code> and <code>word[j+1…i]</code> is valid.