本质上升序列（JAVA）

题目：

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝特别喜欢单调递增的事物。

在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。

例如，在字符串 lanqiao 中，如果取出字符 n 和 q，则 nq 组成一个单调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。 小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 ao，取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。

对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？ 例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。

请问对于以下字符串（共 200200 个小写英文字母，分四行显示）：

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

本质不同的递增子序列有多少个？

运行限制
最大运行时间：1s
最大运行内存: 128M

代码：

import java.util.Arrays;
 
public class Main {
    public static void main(String[] args) {
        String str="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf"+
                   "iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij"+
                   "gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad"+
                   "vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
        int dp[]=new int[str.length()];
        Arrays.fill(dp,1);
        for (int i=0;i<str.length();i++){
            for (int j=0;j<i;j++){
                if (str.charAt(i)>str.charAt(j)){
                    dp[i]=dp[i]+dp[j];
                }
                else{
                    if (str.charAt(i)==str.charAt(j)){
                        dp[i]=dp[i]-dp[j];
                    }
                }
            }
       }
        int sum=0;
        for (int i=0;i<str.length();i++){
            sum+=dp[i];
        }
        System.out.println(sum);
    }
}

思路：

本题采用了动态规划思想

dp[i]表示以第i个字母结尾的上升序列有多少个

举个例子abcdca

dp[1]=1 a

dp[2]=2 b ab

dp[3]=4 c ac bc abc

dp[4]=8 d ad bd abd cd acd bcd abcd

dp[5]=0

dp[6]=0

首先我们将dp全部初始化为1（因为每个字母本身就是一个上升序列）

然后从头开始遍历，

for (int i=0;i<str.length();i++)
再从前往后遍历到i

for (int j=0;j<i;j++)
如果第i个字母大于第j个字母，那么就将第j个字母每一种排列后都可以加上第i个字母也就是

if (str.charAt(i)>str.charAt(j)){
dp[i]=dp[i]+dp[j];
}
如果第i个字母小于第j个字母那么就不是单调递增不用考虑

如果第i个字母等于第j个字母我们以上面例子来讲，第二个c出现时之前一个c已经把前个字母的上升序列全组合过了，第二个c要是再与前三个字母组合就重复了。例如第一个字母与第三个字母组合为ac，第一个字母与第五个字母组合也为ac，就重复了，所以我们要将重复部分减去（这也就是我们为什么将初始值全设为1）

if (str.charAt(i)==str.charAt(j)){
dp[i]=dp[i]-dp[j];
}
然后我们将每个字母结尾的上升序列的组合数加起来就得到了总数，输出即可。

注：上升序列要求单调递增，所以acc这一类的都不是上升序列。