最长上升子序列
之前我定义的dp是：
dp[n][i]：表示在前n个数中选，并以数a[i]结尾的最长上升序列
但是这个状态的转移有点不自然，感觉就想有很多多余的感觉
if (i<=n-1)
dp[n][i]=dp[n-1][i]
if (a[i]>a[j] && j<=n-1)
dp[n][i]=max(dp[n][i],dp[n-1][j]+1)
最长上升子序列一定会在某个下标处结尾的
所以我们可以定义dp是：
dp[i]:表示在前i个数中选，并以a[i]结尾的最长上升序列
这个定义与我上面的不同的是：删去了多余的一维，想一下
其实如果以a[i]结尾，那么不就一定是在前i个数中选吗？
为何还要多此一举定义个n？
于是这个状态转移的方式是：
dp[i]=1;
if (a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1)
除了动态规划这种方法外还有贪心+二分的方法
但是这个正确性我不知道咋证明，用的感觉很怪，我就现在还不懂
博客<----
题目<----
标签：----,结尾,中选,蓝桥,序列,动态,最长,dp,定义 From： https://www.cnblogs.com/cilinmengye/p/17456715.html