這道題我第一眼反應就是暴力，但是暴力的話就是n*n-1*n-2*...n-(n-1) 也就是O(n^n)dfs做絕對超時
貪心也不行，這里是子序列，要考慮在ni的范圍內考慮多種路線取最優，所以用動態規劃
如何用動態規劃呢？
答：建立dp數組：每個dp存放0-i范圍的子序列的最長遞增子序列長度
用兩個for循環
為什么不能用一個for循環？
答：比如0的長度為1，0-1的的最長子序列長度為1或者2
那0-3的最長子序列的長度就是3(nums3>nums2)或者2了嘛
這個只限于子串，子序列比較特殊，這里很難舉例特殊例子，直接說明：
每個dp【i】代表著經過的路徑，可以看成遞歸的歸的父節點，dp【3】存放的可能是【2-3】，【1-3】【1-2-3】
所以用兩個for循環外層為子序列最后結尾的最長長度，里層就遍歷所有的子序列（因為每個dp【i】存放的是最優路徑，所以dp[i]=max(dp[i],dp[j]+1) max里面 dp[i]就是上個子序列dp[j]+1，和現在dpj的最優路徑加上nums【i】構成的子序列比較長度
//這里舉例的數字是 1 3 5 8
題目
#include <vector>
#include <algorithm>class Solution {
public:int lengthOfLIS(std::vector<int>& nums) {int n = nums.size();if (n == 0) return 0;std::vector<int> dp(n, 1); int ans = 1;for(int i=1;i<n;i++){ for(int j=0;j<i;j++){if(nums[i]>nums[j]){dp[i]=max(dp[i],dp[j]+1);}}ans=max(ans,dp[i]);}return ans;}
};
)
