解题思路: 从后向前递推,多写一些情况就能发现规律
dp[i]=value 表示从最后一项到第i项的和为value
last 表示这一次累加的和
dp[i]=dp[i+1]+last;
last 只与上一次的last有关,并且last的值更新有两种情况:
1 未出现相同字母
2 如果出现相同字母,那就只与最近出现的相同字母位置有关
注意事项:
参考代码:
import java.util.Scanner;
public class 子串分值和 {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
String str=scanner.next();
int []latter=new int[200];
long dp[] = new long[str.length()];
dp[str.length()-1]=1;
latter[str.charAt(str.length()-1)]=1;
long last=1;
for(int i=str.length()-2;i>=0;i--){
if(latter[str.charAt(i)]==0)
{
last=last+str.length()-i;
}
else{
int loc=-1;
for(int k=i+1;k<=str.length()-1;k++)
{
if(str.charAt(k)==str.charAt(i)){
loc=k;
break;
}
}
last=last+loc-i;
}
dp[i]=dp[i+1]+last;
latter[str.charAt(i)]=1;
}
System.out.println(dp[0]);
// System.out.println(Arrays.toString(dp));
}
}
0.0分
1 人评分
Tom数 (C++代码)浏览:828 |
数组输出 (C语言代码)--此题的题目描述有问题浏览:1817 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:619 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:476 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:586 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:2092 |
1124题解浏览:595 |
字符逆序 (C语言代码)浏览:621 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:573 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:532 |