题目描述 求一个字符串的最长递增子序列的长度 如：dabdbf 最长递增子序列就是 abdf，长度为 4 输入描述 第一行一个整数 0<n<20, 表示有 n 个字符串要处理 随后的 n 行，每行有一个字符串，该字符串的长度不会超过 10000

这道题可以使用动态规划来解决。设 dp[i] 表示以第 i 个字符结尾的最长递增子序列的长度，那么对于第 i 个字符，可以从前面的所有比它小的字符中找到一个最长的递增子序列，然后加上它自己这个字符，就是以它结尾的最长递增子序列的长度。因此，状态转移方程为：

dp[i] = max(dp[j] + 1)，其中 j < i 且 s[j] < s[i]

最终的答案就是 dp 数组中的最大值。

下面是 Python 的代码实现：

相关问题

求一个字符串的最长递增子序列的长度 如：dabdbf 最长递增子序列就是 abdf，长度为 4

这是一个经典的动态规划问题。可以使用一个一维数组dp来记录以每个字符结尾的最长递增子序列的长度。初始时，每个字符自成一个长度为1的递增子序列，即dp数组全为1。然后遍历字符串，对于每个字符，再遍历它前面的所有字符，如果比当前字符小，则可以将当前字符接到这个字符的子序列后面形成一个新的递增子序列，更新dp数组。最后dp数组中的最大值就是所求的最长递增子序列的长度。以下是示例代码：

def longest_increasing_subsequence(s):
    n = len(s)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if s[j] < s[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# 示例
s = 'dabdbf'
print(longest_increasing_subsequence(s)) # 输出 4

题目描述 求一个字符串的最长递增子序列的长度 如：dabdbf 最长递增子序列就是 abdf，长度为 4 输入描述 第一行一个整数 0<n<20, 表示有 n 个字符串要处理 随后的 n 行，每行有一个字符串，该字符串的长度不会超过 10000 输出描述 输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklmncdefg 样例输出 1 3 7

你可以按照上面的思路，对每个字符串分别求解最长递增子序列的长度。以下是示例代码：

def longest_increasing_subsequence(s):
    n = len(s)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if s[j] < s[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# 主函数
n = int(input())
for i in range(n):
    s = input().strip()
    print(longest_increasing_subsequence(s))

输入示例：

3
aaa
ababc
abklmncdefg

输出示例：

1
3
7