官网站内优化怎么做 2018/游戏优化是什么意思

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印同一个字符序列。
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。
给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。

示例 1:

输入: "aaabbb"
输出: 2
解释: 首先打印 "aaa" 然后打印 "bbb"。
示例 2:

输入: "aba"
输出: 2
解释: 首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
提示: 输入字符串的长度不会超过 100。

思路：动态规划。dp(i, j) 指的是打印 S[i], S[i+1], ..., S[j] 所需的次数。我们需要按以下顺序进行推断：无论在第几次打印字母 S[i]，可能在第一次被打印，也可能单独打印，因为在间隔 [i，k] 上的任何后续打印都可以在 [i+1，k] 上完成。假设第一次打印在 [i, k] 上，则有 s[i]==s[k]，因为如果不是，我们可以打印 [i，k] 中最后出现的 s[i] 以获得相同的结果。当在 [i，k] 中正确打印所有内容时（s[i]==s[k]），它将采取与在 [i，k-1] 中正确打印所有内容相同的步骤。

class Solution {private int[][] dp;public int strangePrinter(String s) {if(s.length()<=1) return s.length();int n=s.length();dp=new int[n][n];return DP(s,0,n-1);}private int DP(String s,int l,int r) {if(l>r) return 0;if(dp[l][r]==0) {int ans=DP(s,l+1,r)+1;for(int k=l+1;k<=r;k++) {if(s.charAt(k)==s.charAt(l))ans=Math.min(ans, DP(s,l,k-1)+DP(s,k+1,r));}dp[l][r]=ans;}return dp[l][r];}
}