DP--最长上升子序列（线性-单串）

目录

题号

思路

    状态定义：dp[i]表示在数组nums中以第i位置为结尾的最长上升子序列

    转移方程：

        在计算dp[i]之前，我们通过计算，已知dp[0]......dp[i-1]的值

        由于dp[i-1]代表以i-1结尾的最长上升序列

        则，当nums[i]>nums[i-1]时，有几率形成更长的上升序列

        只需要将当前nums[i]分别并入dep[0......i-1]中，看是否能形成更优序列即可

        即当前i依赖比i小的O(n)个子问题

        故，转移方程为：dp[i] = max(dp[0......i-1])+1

    初始状态：

        由于至少存在一个元素使得dp[i]满足子序列，故初始为1

    边界：

        nums[i]>nums[i-1]

实现

（外层循环确定范围，内层循环做子问题最优解合并）