# Python, Straightforward DP with Explanation

• Let `dp(i, j)` be the number of turns needed to print `S[i:j+1]`.

Note that whichever turn creates the final print of S[i], might as well be the first turn, and also there might as well only be one print, since any later prints on interval [i, k] could just be on [i+1, k].

So suppose our first print was on [i, k]. We only need to consider prints where S[i] == S[k], because we could instead take our first turn by printing up to the last printed index where S[k] == S[i] to get the same result.

Then, when trying to complete the printing of interval [i, k] (with S[i] == S[k]), the job will take the same number of turns as painting [i, k-1]. This is because it is always at least as good to print [i, k] first in one turn rather than separately.

Also, we would need to complete [k+1, j]. So in total, our candidate answer is dp(i, k-1) + dp(k+1, j). Of course, when k == i, our candidate is 1 + dp(i+1, j): we paint S[i] in one turn, then paint the rest in dp(i+1, j) turns.

``````def strangePrinter(self, S):
memo = {}
def dp(i, j):
if i > j: return 0
if (i, j) not in memo:
ans = dp(i+1, j) + 1
for k in xrange(i+1, j+1):
if S[k] == S[i]:
ans = min(ans, dp(i, k-1) + dp(k+1, j))
memo[i, j] = ans
return memo[i, j]

return dp(0, len(S) - 1)
``````

• @awice
I wonder why it's not correct for `ans = min(ans, 1 + dp(i+1, k-1) + dp(k+1, j))`

• Because you can have d[i, k-1] = d[i+1, k-1], but you assume that d[i, k-1] = 1+d[i+1, k-1]. Check this @awice 's argument as well:

"Then, when trying to complete the printing of interval [i, k] (with S[i] == S[k]), the job will take the same number of turns as painting [i, k-1]. This is because it is always at least as good to print [i, k] first in one turn rather than separately."

• edit:
I used to have a proof here. It was flawed.
I'll need to go back to the drawing boards to come up with a correct proof.

UPDATE: done

• Let dp(i, j) be the number of turns needed to print S[i:j+1].

why not Let dp(i, j) be the number of turns needed to print S[i:j]?

• @yezilife It is more natural to work in exact intervals like `[i, j]`. So letting `dp(i, j) = answer for S[i], S[i+1], ..., S[j]` is easier for me than letting `dp(i, j) = answer for S[i], S[i+1], ..., S[j-1]`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.