(动态规划最长递增的子序列）leetcode300

这道题我第一眼反应就是暴力，但是暴力的话就是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; } };