LeetCode 300. 最长递增子序列

LeetCode 300. 最长递增子序列

Idea

最长递增子序列，首先就想到了LCS（最长公共子序列），这个其实比最长公共子序列还简单。

定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度。

状态转移方程： d p [ i ] = max ⁡ ( d p [ j ] ) + 1 ,  其中  0 ≤ j < i  且  num ⁡ [ j ] < num ⁡ [ i ] d p[i]=\max (d p[j])+1, \text { 其中 } 0 \leq j