题解 | 动态规划#Redraiment的走法#

假设 dp[i]为终点为第i个桩的最大走法

那么比较之前num[j]中比num[i]小的桩的最大走法：

如果 num[j]< num[i],那么就有两种情况：

1. 踩上j桩： dp[i] = 1 + dp[j]
2. 不踩，忽略： dp[i] = dp[i] （原数量不变）

取两个情况的最大值

while True:
    try:
        n = int(input())
        s = list(map(int,input().split()))
        dp= [1] *n
        for i in range(n):
            for j in range(i):
                if s[i]>s[j]:
                    dp[i] = max(1+dp[j],dp[i])
        print(max(dp))
    except:
        break