蓝桥杯-本质上升序列(动态规划问题)
本质上升序列-动态规划问题
1、题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝特别喜欢单调递增的事物。
在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。
例如，在字符串 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
2、解题思路
以dp[i]表示以str[i]结尾的本质不同递增子序列的个数，我们考虑j<i的情况，
：
- 当
,则
,因为dp[j]表示以str[j]结尾的递增子序列个数，又因为
，则在str[j]子序列的末尾拼接上str[i]所得到的子序列一定包含在dp[i]对应的结果集中。
- 当
,则
,此时说明
的递增序列是重复的，我们应当减去这一部分，下面会给个实例。或者也可以这么理解，当str[i]==str[j]的时候，dp[i]数组按照定义应该是不改变的,但是我们最终要统计总和，如果不减去dp[j]，那么最后计算的时候dp[j]部分会被重复累加，具体可以看下表。
- 当
，这是倒序，不满足条件。
由于单个字符也算递增子序列，所以
dp数组初始化为1
我们以一个数字串来描述，比字符串更直观，假设我们现在有串
。
str[i] | dp | 递增子序列的值 |
|---|---|---|
1 | dp[0]=1 | 1 |
2 | dp[1]=2 | 2,12 |
7 | dp[2]=4 | 7,17,27,127 |
8 | dp[3]=7 | 8,18,28,78,128,178,278 |
3 | dp[4]=4 | 3,13,23,123 |
7 | dp[5]=8-4=4 | 7,17,27,37,127,137,237,1237 |
从上表中可以看到，str[i]=7的时候重复了，这也是为什么上面当
,有
了。
3、代码实现
import java.util.Arrays;
//dp[i]表示以str[i]结尾的本质不同递增子序列的个数
//考虑j<i
//当str[j]<str[i],dp[i]=dp[i]+dp[j]
//当str[j]=str[i],dp[i]=dp[i]-dp[j]
//当str[j]>str[i],此时是降序，不考虑
public class Main {
public static void main(String[] args) {
String str = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf" +
"iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij" +
"gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad" +
"vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
// String str="127837";
int[] dp = new int[str.length()];
//由于单个字符也算递增序列，所以dp初始化为1
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[j];
}else if(str.charAt(i)==str.charAt(j)){
dp[i]-=dp[j];
}
}
}
System.out.println(Arrays.stream(dp).sum());
}
}