找网站建设公司需要注意什么,商务网站建设试卷,免费云服务器网站有哪些,wordpress上传的地址加题目
有台奇怪的打印机有以下两个特殊要求#xff1a;
打印机每次只能打印由 同一个字符 组成的序列。 每次可以在任意起始和结束位置打印新字符#xff0c;并且会覆盖掉原来已有的字符。 给你一个字符串 s #xff0c;你的任务是计算这个打印机打印它需要的最少打印次数。…题目
有台奇怪的打印机有以下两个特殊要求
打印机每次只能打印由 同一个字符 组成的序列。 每次可以在任意起始和结束位置打印新字符并且会覆盖掉原来已有的字符。 给你一个字符串 s 你的任务是计算这个打印机打印它需要的最少打印次数。
示例 1
输入s “aaabbb” 输出2 解释首先打印 “aaa” 然后打印 “bbb”。 示例 2
输入s “aba” 输出2 解释首先打印 “aaa” 然后在第二个位置打印 “b” 覆盖掉原来的字符 ‘a’。
解题思路
数组含义
这题的数组的含义应该很容易就看得出来dp[i][j]代表子串s[i,j]的最少打印次数
状态转移
例如字符串aba在计算dp[i][j]dp[0][2]时 遍历rirj-1,检查s[r]s[j],如果s[r]s[j]的话就是说明了可能有一种情况是 先打印子串s[i…j],然后再将子串s[r1…j-1]覆盖掉所以状态转移方程就是 dp[i][j] Math.min(dp[i][j],dp[i][r]dp[r1][j-1]);
第一步时打印子串s[i…j]的最少打印次数dp[i][r]因为第一步时子串s[r1,j]里面的所有元素都是等于s[r]的结合题目条件打印机每次只能打印由 同一个字符组成的序列和s[r]s[j]可得所以dp[i][j]dp[r1][j]是成立的第二步时将子串s[r1…j-1]进行打印然后覆盖在第一步的结果上因此第二步的打印次数就是dp[r1][j-1] 将两步的打印次数相加就是这种情况下的打印次数
初始化
dp[i][i]直接初始化为1因为一个字符只需要一次打印其他还没填充的元素均置为最大值。
代码
class Solution {public int strangePrinter(String s) {int[][] dp new int[n 1][n 1];for (int i 0; i n; i) Arrays.fill(dp[i],Integer.MAX_VALUE);for (int i 0; i n; i) dp[i][i]1;for (int i n-1; i 0; i--) {for (int j i1; j n; j) {char cur s.charAt(j);if (curs.charAt(j-1))dp[i][j]dp[i][j-1];else {dp[i][j]dp[i][j-1]1; for (int rj-2;ri;r--){if(cur!s.charAt(r)) continue;dp[i][j] Math.min(dp[i][j],dp[i][r]dp[r1][j-1]);}}}}return dp[0][n-1];}
}结果
