leetcode刷题系列

原题链接: 戳这里.

代码

class Solution: def strangePrinter(self, s: str) -> int: dp={} def getdp(i,j): if i>j: # 递归的终止条件 return 0 ans=1+getdp(i+1,j) # 每次结果最大就是新增的与之前都不同，所以加1 if (i,j) not in dp: # 不在就需要计算 for k in range(i+1,j+1): if s[i]==s[k]: ans = min (ans,getdp(i+1,k)+getdp(k+1,j)) dp[i,j]=ans return dp[i,j] return getdp(0,len(s)-1)

题解

区间dp主要的思想就是要明白，二维的dp解决不了问题了，一定要引入多一次的循环，为什么二维dp解决不了了呢？ 对于此问题，dp数组的值表示i到j 的最小解，那么此解只有两个答案， 要么是i+1到j的解+1，及新增的字母不在i+1到j中 要么是i+1到j的解 那么到底是哪个i+1到j 的字母打印了第i个字母是不确定的 所以应该多来一个循环， k从i到j 即三重循环