class Solution {
public int strangePrinter(String s) {
if(s.length()==0)return 0;
int n = s.length();
int dp[][] = new int [n][n];
// for(int i = 0 ; i < n ; i++ ) { //当然这一步可以放在下面for循环里面
// dp[i][i] = 1 ; //每一步都是打印一次 也就是染一次 最坏情况
// }
for(int j =0 ; j < n; j++ ) { //开始到结尾的截断字符串长度 //上面没有注释 则 j = 1
for(int i = 0 ; i + j < n ; i++) { //从第一位开始dp
dp[i][i+j] = 1 + j; //最坏情况 i + f(i,j):(j - i + 1 )
for(int k = i ; k < i + j ; k++) {
int sum = dp[i][k] + dp[k+1][i+j] ;
if(s.charAt(k)==s.charAt(i+j)) { //直接被覆盖 例如 abaa 所以 后面两个aa可以一起覆盖
sum--;
}
dp[i][j+i] = Math.min(dp[i][i+j], sum);
}
}
}
return dp[0][n-1];
}
}
你好,图片是怎样插入题解的?
其实我是在自己牛客博客上写的题解 然后直接拷贝到这里过来 ,貌似这个网站还不支持图片直接复制进来自己生成图片链接 但是支持图片插入markdown语法
好的,谢谢,不会markdown语法的可以通过按钮,上传本地图片,会生成markdown语法
上传太麻烦了 因为是qq截图 所以在其他网站上就可以直接截图 粘贴 不用上传