解题思路: 从后向前递推,多写一些情况就能发现规律
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 人评分
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:718 |
【出圈】 (C语言代码)用单项循环链表浏览:814 |
C语言程序设计教程(第三版)课后习题6.9 (C++代码)论pow函数的应用浏览:1067 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:685 |
字符串输入输出函数 (Java代码)浏览:1480 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:635 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1059 |
P1001 (C语言代码)浏览:830 |
三角形 (C++代码)递推浏览:813 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:714 |