题解 | #最长上升子序列(一)#
最长上升子序列(一)
https://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f
2022.0816算法第29题最长上升子序列(一)
子序列不好使用暴力解法，主要是子序列的方案太多了。
采用动态规划进行求解。
1、状态矩阵dp
存储子序列末尾位置的最大长度，并且初始化为1.
vector<int> dp(arr.size(),1);2、初始值
dp[0]=1;
3、状态转移方程
dp[i]=max(dp[i],dp[j]+1);这个转移方程还是不容易想出来的，
for(int i=1;i<arr.size();i++){
for(int j=0;j<i;j++){
//以下语句能够确保得到最接近arr[i]的数字
//在小于当前值时，不断更新dp[i]的值，获取其中最大值
if(arr[j]<arr[i])
dp[i]=max(dp[i],dp[j]+1);
}
}
是对当前数字节点前的数字进行遍历
找出最接近当前数字的值对应的dp[j]然后加上本身1；
得物app公司福利 402人发布
