蓝桥杯-本质上升序列(动态规划问题)

本质上升序列-动态规划问题

• 1、题目描述
• 2、解题思路
• 3、代码实现

• 参考

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 个小写英文字母，分四行显示）：

代码语言：javascript复制

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

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

运行限制

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

2、解题思路

  以dp[i]表示以str[i]结尾的本质不同递增子序列的个数，我们考虑j<i的情况，

j=0sim i-1

：

• 当

str[i]>str[j]

,则

dp[i]=dp[i] dp[j]

,因为dp[j]表示以str[j]结尾的递增子序列个数，又因为

str[i]>str[j]

，则在str[j]子序列的末尾拼接上str[i]所得到的子序列一定包含在dp[i]对应的结果集中。

• 当

str[i]==str[j]

,则

dp[i]=dp[i]-dp[j]

,此时说明

0sim j

的递增序列是重复的，我们应当减去这一部分，下面会给个实例。或者也可以这么理解，当str[i]==str[j]的时候，dp[i]数组按照定义应该是不改变的,但是我们最终要统计总和，如果不减去dp[j]，那么最后计算的时候dp[j]部分会被重复累加，具体可以看下表。

• 当

str[i]<str[j]

，这是倒序，不满足条件。

  由于单个字符也算递增子序列，所以dp数组初始化为1

  我们以一个数字串来描述，比字符串更直观，假设我们现在有串

1,2,7,8,3,7

。

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的时候重复了，这也是为什么上面当

str[i]==str[j]

,有

dp[i]=dp[i]-dp[j]

了。

3、代码实现

代码语言：javascript复制

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

dp 动态规划 数组 统计 字符串

0 人点赞