Redraiment的走法

def count(n,nums,res):
    for i in range(2,n+1):
        for j in range(1,i):
            if nums[-i]<nums[-j] and res[-i]<res[-j]+1:
                res[-i]=res[-j]+1
    return max(res)
while True:
    try:
        n=int(input())
        nums = [int(x) for x in input().split()]
    except:
        break
    res=[1]*n
    print(count(n,nums,res))

def scan_index(input_list,index_value):
    result = []
    for k,v in enumerate(input_list[:index_value]):
        if v<input_list[index_value]:
            result.append(k)
    return result
while True:
    try:
        input_len = len(input())
        input_value =input().split()
    except:break

    max_dict = {}
    input_value = list(map(int,input_value))
    for k,v in enumerate(input_value):
        v_min_index = scan_index(input_value,k)
        if len(v_min_index)==0:
            max_dict[k]=1
        else:
            max_dict[k] = max([max_dict[j] for j in v_min_index])+1
    print(max(max_dict.values()))
        

dp = dict()
def getMaxSub(lst, minNum):
    tup = tuple(lst)
    outer = (tup, minNum)
    if outer in dp:
        return dp[outer]
    #print('This is lst: {}'.format(lst))
    if len(lst) == 1:
        if minNum == None or minNum < lst[0]:
            dp[outer] = 1
            return 1
        dp[outer] = 0
        return 0
    if minNum == None:
        num = max(1 + getMaxSub(lst[1:], lst[0]), getMaxSub(lst[1:], None))
        dp[outer] = num
        return num
    else:
        cur = lst[0]
        if cur > minNum:
            num = max(1 + getMaxSub(lst[1:], cur), getMaxSub(lst[1:], minNum))
            dp[outer] = num
            return num
        else:
            num = getMaxSub(lst[1:], minNum)
            dp[outer] = num
            return num

lst = []
while True:
    try:
        input()
        string = input()
        string = string.split()
        newLst = []
        for i in string:
            newLst.append(int(i))
        lst.append(newLst)
    except:
        break

for i in lst:
    print(getMaxSub(i, None))

给一个python的解法。本身就是一个recursion，一开始不用dp会timeout，原因是getMaxSub(sublist, None) 出现次数过多，造成重复运算。所以用dictionary做了一个简易dp

import bisect


while True:
    try:
        n, nums = int(input()), map(int, input().split())
        temp = []
        for i in nums:
            pos = bisect.bisect_left(temp, i)
            if pos == len(temp):
                temp.append(i)
            else:
                temp[pos] = i
        print(len(temp))
    except:
        break

while True:
    try:
        n = int(input())
        s = input().split()
        s = [int(i) for i in s]
        res = []
        for i in range(len(s)):
            c = 1
            a = s[i]
            if i+1 < len(s):
                tem = sorted(s[i+1:])
            else:
                res.append(c)
                break
            for j in tem:
                if j > a:
                    a = j
                    c += 1
            res.append(c)
#         print(res)
        print(max(res))
    except:
        break

# 确定状态 最后一步a[j]
# 1. 最优策略中的最长上升子序列就是{a[j]} 答案是 1
# 2. 子序列长度大于 1，那么最优策略中，a[j] 前一个元素是 a[i] 且 a[i] < a[j]
# 因为是最优策略，那么以 a[i] 结尾的子序列一定是最长的
# 不知道 a[i] 是哪一个，所以枚举每个 i 
# 问题变为求 以a[i] 结尾的最长子序列
# 得出状态 f[j] = 以 a[j] 结尾的最长子序列的长度
# 转移方程 f[j] = max{1, f[i] + 1 且 i<j and a[i] < a[j]}
# 计算f[0] f[1] ......f[n-1] 然后取最大值
while True:
    try:
        n, A = int(input()), list(map(int, input().split()))
        if n <= 0:
            print('0')
        else:
            res = 0
            f = [1] * n
            for j in range(n):
                for i in range(j):
                    if A[i] < A[j] and f[i] + 1 > f[j]:
                        f[j] = f[i] + 1
                res = max(res, f[j])
            print(res)
    except:
        break
        

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

import bisect
while True:
    try:
        a, b = int(input()), map(int, input().split())
        q = []
        for v in b:
            pos = bisect.bisect_left(q, v)
            if pos == len(q):
                q.append(v)
            else:
                q[pos] = v
        print(len(q))
    except:
        break
# 凡哥作品
#解释:
#相当于维护一个结果数组，如果当前元素比结果数组的值都大的的话，就追加在结果数组后面
#（相当于递增序列长度加了1）；否则的话用当前元素覆盖掉第一个比它大的元素
#（这样做的话后续递增序列才有可能更长，即使并没有更长，这个覆盖操作也并没有副作用哈，
#当然这个覆盖操作可能会让最终的结果数组值并不是最终的递增序列值，这无所谓）
#https://leetcode-cn.com/problems/longest-increasing-subsequence/comments/284831

"""
Create Time: 2020/6/15 10:59
Author: FengkaiXiao
"""
"""
Create Time: 2020/6/15 10:59
Author: FengkaiXiao
"""
import bisect
def meihuazhaung():
	while True:
		try:
			a, b = int(input()), map(int, input().split())
			q = []
			for v in b:
				pos = bisect.bisect_left(q, v)
				if pos == len(q):
					q.append(v)
				else:
					q[pos] = v
			print(len(q))
		except:
			break
meihuazhaung()

while True:
    try:
        n = int(input())
        container = []
        container = input().split()
        container = [int(x) for x in container]
        dp = [0]*n
        dp[-1] = 1
        res = []
        for j in range(n-2,-1,-1):
            temp = [] 
            for k in range(j,n):
                if container[k] > container[j]:
                    temp.append(1+dp[k])
            if len(temp) == 0:
                temp.append(1)
            dp[j] = max(temp)
        print(max(dp))
    except:
        break