§07 动态规划

最长递增子序列 LIS

dp[i] = 以 a[i] 结尾的 LIS 长度——扫描更小的前驱取最大值加一。

最长递增子序列

第 01 / 9 步

LIS：序列 [10, 9, 2, 5, 3, 7, 101, 18]。dp[i] = 以 a[i] 结尾的最长递增子序列长度，初始全为 1。

伪代码


				
					
					1
					// LIS: dp[i] = 以 i 结尾的最长递增子序列长度
				
			
				
					
					2
					dp[所有] = 1
				
			
				
					
					3
					for i = 1 to n-1:
				
			
				
					
					4
					  for j = 0 to i-1:
				
			
				
					
					5
					    if a[j] < a[i]:
				
			
				
					
					6
					      dp[i] = max(dp[i], dp[j] + 1)
				
			
				
					
					7
					answer = max(dp)

01 / 9

速度