小白刚刚学到动态规划 求大佬解释最长递增子序列python代码的意义，看不懂代码

不是比企谷八幡

def LIS(L):
    ASC=[1]*len(L);Tra=[-1]*len(L)
    for i in range(1,len(L)):
        x=[]
        for j in range(0,i):
            if L[i]>L[j]:
                x.append(j)
        for k in x:
            if ASC[i]<ASC[k]+1:
                ASC[i]=ASC[k]+1;Tra[i]=k
        print("ASC:",ASC)
        print("Tra:",Tra)
        max=0
        for i in range(1,len(ASC)):
            if ASC[i]>ASC[max]:max=i
        print("最长递增子序列长度：",ASC[max])
        x=[L[max]];i=max;
        while (Tra[i]>=0):
            x=[L[Tra[i]]]+x
            i=Tra[i]
        print("最长递增子序列=",x)   
   
递归：
def ASC(k):
    if k==0:return(1)
    x=[]
    for i in range(0,k):
        if l[k]>l[i]:x.append(ASC(i))
    if len(x)>0:return(max(x)+1)
    else:return(1)
def lis(l):
    x=[]
    for k in range(0,len(l)):
        x.append(ASC(k))
    print(x)
    print(max(x))
另外 假如有两个最大递增长度的结果时 怎么同时输出两个结果

Stubborn

把题目贴上来，代码发规范 `<>`用这个发

1. def LIS(L):
   
2.     ASC=[1]*len(L);Tra=[-1]*len(L)
   
3.     for i in range(1,len(L)):

复制代码

不是比企谷八幡

Stubborn 发表于 2019-11-19 18:07
把题目贴上来，代码发规范 ``用这个发

问题描述：已知有n个数的序列L 求他的最长递增子序列长度。假设序列L中的一个递增子序列【a1,a2,..an】这些数必须满足a1<..<ai<..<aj<..<an (1<=i<=j>=k), 而最长递增子序列就是所有递增子序列中长度最长的那个 例如序列L=【5，2，4，7，6，3，8，9】的最长递增子序列是【2，4，7，8，9】长度为5
怎么发成你这种格式

不是比企谷八幡

1. def LIS(L):
   
2.     ASC=[1]*len(L);Tra=[-1]*len(L)
   
3.     for i in range(1,len(L)):
   
4.         x=[]
   
5.         for j in range(0,i):
   
6.             if L[i]>L[j]:
   
7.                 x.append(j)
   
8.         for k in x:
   
9.             if ASC[i]<ASC[k]+1:
   
10.                 ASC[i]=ASC[k]+1;Tra[i]=k
    
11.         print("ASC:",ASC)
    
12.         print("Tra:",Tra)
    
13.         max=0
    
14.         for i in range(1,len(ASC)):
    
15.             if ASC[i]>ASC[max]:max=i
    
16.         print("最长递增子序列长度：",ASC[max])
    
17.         x=[L[max]];i=max;
    
18.         while (Tra[i]>=0):
    
19.             x=[L[Tra[i]]]+x
    
20.             i=Tra[i]
    
21.         print("最长递增子序列=",x)   
    
22.    
    
23. 递归：
    
24. def ASC(k):
    
25.     if k==0:return(1)
    
26.     x=[]
    
27.     for i in range(0,k):
    
28.         if l[k]>l[i]:x.append(ASC(i))
    
29.     if len(x)>0:return(max(x)+1)
    
30.     else:return(1)
    
31. def lis(l):
    
32.     x=[]
    
33.     for k in range(0,len(l)):
    
34.         x.append(ASC(k))
    
35.     print(x)
    
36.     print(max(x))

复制代码

Stubborn

1. def sequence(L:List[int]):
   
2.     """
   
3.     对于DP来说，找出子问题，推出最优解。
   
4.     """
   
5.     length = len(L)
   
6.     dp = [1]
   
7.     for i in range(1,length):
   
8.         dp.append(1)
   
9.         for j in range(0, i):
   
10.             if L[j] < L[i]:
    
11.                 dp[i] = max(dp[i], dp[j]+1)
    
12.     print(dp)

复制代码

这个思路不懂可以继续提问

可以看下我写的这几个题目，可能会加深一点关于DP动规的理解  点击我前进

XiaoPaiShen

从哪学的动态规划？

Stubborn

XiaoPaiShen 发表于 2019-11-20 03:23
从哪学的动态规划？

多做题，多看思路，

阴阳神万物主

XiaoPaiShen 发表于 2019-11-20 03:23
从哪学的动态规划？

本论坛就能学到
https://fishc.com.cn/forum-79-1.html
小甲鱼做过视频，我好些年前买的 U盘里就有
虽然我没有学到那个位置