【动态规划】非降序最长子串

在这个问题中定义什么是状态很重要。
举例来说：dp[4]:表示以输入字符串中第5个字符为结束的字符串中的最长非降序子串的长度。

s = input()
dp = [0 for i in range(len(s))] #初始化状态矩阵
dp[0] = 1  #第一个状态为1
maxL = dp[0]

for i in range(len(s)):
  for j in range(i):
    if s[i] >= s[j]:    #状态转移条件
      dp[i] = max(maxL, dp[j]+1)  #状态转移方程
      maxL = dp[i]
print maxL