11届国赛python试题 D: 本质上升序列
https://www.jianshu.com/p/31cd66789a99
解题思路：
1.找子问题：原问题是从键盘任意输入200个英文字符的序列，求该序列中所有满足递增序列的个数；求解该问题，需要进行问题转换，求解以任意ak英文字母结尾的字符串的递增子序列个数之和；
sumS=sum({a1},{a2},{a3},{a4},{a5.}......{ak}，{an})，求以a1结尾，a2结尾，a3...ak，an结尾的符合递增子序列的个数之和；
2.状态转移方程：
设以ak字符结尾的递增子字符串序列的个数dp[k]，该字符串序列用数学通向表示为{a1,a2,a3..........ak-1,ak}.
以ak-1字符结尾的递增子字符串序列的个数dp[k-1],该字符串序列用数学通向表示为{a1,a2,a3......ak-1}.
如果ak-1字符序列的所有元素都比ak小，则添加上ak必然是一个递增序列，之前的dp[k-1]个数生效被累加；
dp[k]=dp[k]+dp[k-1],
3.关键代码撰写；
for(k=1,k<=N,k++)
for(j=1;j<k;j++)
if(s[k]>s[j])
dp[k]+=dp[j]
if(s[k]==s[i])
dp[k]-=dp[j]
