【問題描述】
小藍特別喜歡單調遞增的事物。
在一個字符串中，如果取出若干個字符，將這些字符按照在字符串中的順
序排列后是單調遞增的，則成為這個字符串中的一個單調遞增子序列。
例如，在字符串 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。

請問對于以下字符串:

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

本質不同的遞增子序列有多少個？

解題思路:
1.動態規劃：建立dp數組,dp[i]表示以num[i]為結尾的子序列個數
滿足添加的num[i]：
我們動態規劃的轉移條件就2個。
一個是滿足題目要求的時候，一個是相等時，當題目字母相等時前面的字母已經累加過一次的，所以我們要把前累計過的去掉，和去重一樣的關系。
A:假如num[j]是小于num[i]的,
那么dp[i]=dp[i]+dp[j]就是我們要求的答案。
B:假如numj是等于num[i]的
dp[i]=dp[i]-dp[j]
因為每一個字母都算一個序列，所以dp初始化為1

代碼如下:

#include <iostream> #include <cstring> using namespace std; const int N = 200; typedef long long LL; int dp[N]; string str ="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";int main() {for (int i = 0; i < N; i++)dp[i] = 1;for (int i = 1; i < N; i++)for (int j = 0; j < i; j++) {if (str[i] > str[j])dp[i] += dp[j];else if (str[i] == str[j])dp[i] -= dp[j];}LL ans = 0;for (int i = 0; i < N; i++)ans += dp[i];cout << ans << endl;return 0; }

總結

以上是生活随笔為你收集整理的十一届蓝桥杯国赛 本质上升序列-dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。