[LeetCode]Strange Printer

这道题也是DP的问题，如果我们用dp[i][j]表示print s[i:j]子串需要的最少次数的话，我们可以有递推方程：

• dp[i][j] = min(1 + dp[i + 1][j], min(dp[i][k - 1] + dp[k + 1][j])), where i < k <= j && s[i] == s[k]

这个递推公式很好理解。首先我们可以直接花一次print s[i]的字符，这样的话就是1 + dp[i + 1][j]。此外，如果[i + 1, j]当中存在k，s[i] == s[k]，那么s[k]其实可以不需要额外的次数，可以直接和s[i]一起print出来，那么这样的的话，就对应dp[i][k - 1] + dp[k + 1][j]。我们可以看出来这是一个区间DP的问题。时间复杂度O(n^3)，空间复杂度O(n^2)。代码如下：