蓝桥杯2020年第十一届省赛真题-子串分值和 dp 思路简单

解题思路: 从后向前递推，多写一些情况就能发现规律

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));
   }
}