沒有白走的路，每一步都算數(shù)🎈🎈🎈

題目描述：

小藍(lán)特別喜歡單調(diào)遞增的事物

在一個字符串中如果取出若干個字符，按照在原來字符串中的順序排列在一起，組成的新的字符串如果是單調(diào)遞增的，那么則稱這個字符串為一為一個單調(diào)遞增子序列。但是對于lanqiao字符串，

單調(diào)子序列可以有l(wèi),a,n,q,i,o;

ao,io,q,nq,no,ai,aq,an,aio,ano,anq;

lo,ln,lq,lnq

但是，第一個‘a(chǎn)’能夠和‘o’組成一個單調(diào)遞增子序列，倒數(shù)第一個‘a(chǎn)’也能和‘o’組成一個子序列，我們稱這樣的序列本質(zhì)上是相同的。求問總共有多少本質(zhì)不同的單調(diào)上升子序列

輸入描述：

輸入一個字符串s,字符串總共有4行，每行50個字母，總共有200個字母。試求這個字符串的本質(zhì)上升序列總共有多少？

樣例輸入輸出：

樣例輸入:

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

算法設(shè)計(jì)：

從后往前找，一個字符一個字符累加。遇到不相同的并且后面字母比前面大的就累加，遇到相同的則需要減去相同的字符串。

import os
import sys
s = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl"
dp = [0]*200
n = len(s)
cnt = 0
for i in range(n-1,-1,-1):dp[i] = 1for j in range(i+1,n):if s[i]<s[j]:dp[i]+=dp[j]elif s[i]==s[j]:dp[i]-=dp[j]cnt+=dp[i]
print(cnt)

每日一句

摘自《平凡的世界》：

人生啊，是這樣不可預(yù)測，沒有永恒的痛苦，也沒有永恒的幸福，生活像流水一般，有時(shí)是那么平展，有時(shí)又是那么曲折。