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

举报
别团等shy哥发育 发表于 2023/04/04 23:09:43 2023/04/04
【摘要】 @toc 1、题目描述本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。小蓝特别喜欢单调递增的事物。在一个字符串中,如果取出若干个字符,将这些字符按照在字符串中的顺序排列后是单调递增的,则成为这个字符串中的一个单调递增子序列。例如,在字符串 lanqiao 中,如果取出字符 n 和 q,则 nq 组成一个单调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等...

@toc

1、题目描述

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

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

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

例如,在字符串 lanqiao 中,如果取出字符 nq,则 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的情况, j = 0 i 1 j=0\sim i-1

  • s t r [ i ] > s t r [ j ] str[i]>str[j] ,则 d p [ i ] = d p [ i ] + d p [ j ] dp[i]=dp[i]+dp[j] ,因为dp[j]表示以str[j]结尾的递增子序列个数,又因为 s t r [ i ] > s t r [ j ] str[i]>str[j] ,则在str[j]子序列的末尾拼接上str[i]所得到的子序列一定包含在dp[i]对应的结果集中。
  • s t r [ i ] = = s t r [ j ] str[i]==str[j] ,则 d p [ i ] = d p [ i ] d p [ j ] dp[i]=dp[i]-dp[j] ,此时说明 0 j 0\sim j 的递增序列是重复的,我们应当减去这一部分,下面会给个实例。或者也可以这么理解,当str[i]==str[j]的时候,dp[i]数组按照定义应该是不改变的,但是我们最终要统计总和,如果不减去dp[j],那么最后计算的时候dp[j]部分会被重复累加,具体可以看下表。
  • s t r [ i ] < s t r [ j ] str[i]<str[j] ,这是倒序,不满足条件。

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

我们以一个数字串来描述,比字符串更直观,假设我们现在有串 1 , 2 , 7 , 8 , 3 , 7 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的时候重复了,这也是为什么上面当 s t r [ i ] = = s t r [ j ] str[i]==str[j] ,有 d p [ i ] = d p [ i ] d p [ j ] dp[i]=dp[i]-dp[j] 了。

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

image-20230323171107859

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。