奇怪的打印机

本质还是基于跨域的s[i]==s[k]对dp解的优化

• 为了避免dp[i][j]初始值为0影响min判断需要初始化该点为dp[i][j]=min(j-i+1,dp[i+1,j]+1)

• 对于s=1213，s[0]与s[2]相等，从0到k=2连续打印1是最优解，所以可以将[0,k-1]（删除k不会影响打印的次数，只要还是为了避免j==k的情况）与[k+1,3]划分为两段求最优解，dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j])

• 如果s[0]与s[2]不相等，那么试试别的k取值能不能优化dp

class Solution:
    dp=[]
    def helper(self,ss,dp,x,y):
        if x>y:
            return 0
        if x==y:
            return 1
        if dp[x][y]!=0:
            return dp[x][y]
        # 当k!=x的时候，k与x相等可以对dp优化,k并入x的打印过程中
        # 当k==x的时候说明该点不存在优化可能，但是后面[x+1,y]说不定有,for循环里面无法适配该情况得单列
        dp[x][y]=min(y-x+1,self.helper(ss,dp,x+1,y)+1)
        # 如果没法优化那就默认一个点打印一次y-x+1
        # if ss[x]==ss[y]:
        #     dp[x][y]=min(dp[x][y],self.helper(ss,dp,x,y-1))
        for k in range(x+1,y+1):
            if ss[x]==ss[k]:
                dp[x][y]=min(dp[x][y],self.helper(ss,dp,x,k-1)+self.helper(ss,dp,k+1,y))
        return dp[x][y]
    def strangePrinter(self, s: str) -> int:
        if s=="":
            return 0
        ss=s[0]
        # 合并重复的连续字符因为不影响打印次数
        for i in range(1,len(s)):
            if s[i]!=s[i-1]:
                ss+=s[i]
        length=len(ss)
        dp=[[0]*length for  i in range(length)]
        return self.helper(ss,dp,0,length-1)