Strange Printer

class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        dp =[[0]*n for i in range(n)]
        for i in range(n-1,-1,-1):         ## i: start point of string
           for j in range(i,n):            ## j: end point of string
                if i==j:                   ## if there is single character, it's a base case
                    dp[i][j]=1
                else:
                    if j>=1 and s[j]==s[j-1]:
                        dp[i][j]=dp[i][j-1]
                    else:
                        dp[i][j]= dp[i][j-1]+1
                        for k in range(i, j-1):
                            if s[k]==s[j]:
                                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j-1])
        return dp[i][j]
        
        
        
'''The idea is that if we meet a character same as the previous one, we don't need new moves because the printer 
can print them together. For example, steps ("aa") = steps("a"). However, if we meet a different character,
we have 2 options: option 1: use another step to print that single character, then steps(new string) = steps (old string)+1.

Option 2, if this character also appear in the previous string, we can print it together with previous string.
For example, "aabba", we can print last "a" with first 2 a "aa", then replace it with the string in the middle. 
steps ("aabba") = steps ("aa")+ steps ("bb")

But how do we calculate steps for the string in the middle? The idea is that we can use a 2D matrix to store all substrings. 
More formally, option 2 will become steps[i][j] = steps [k+1][j-1] + steps[i][k], where i means starting index of previous string 
and new string. Index k+1 means starting index of middle string and j means the ending index of our new string. 
Notice that here k is greater than i, therefore we need to iterate form n-1 to 0 instead of 0 to n-1 in order to take 
pre-computed value steps[k+1][j-1].'''