漂亮的flash网站,商户如何做h5商城网站是什么意思,icp备案网站信息查询,下载的网站模版怎么用思路#xff1a;动态规划。
其实这道题和最长递增子序列很像#xff0c;都是以数字为结尾的dp形式#xff0c;也就是把判断条件改了一下就是了。
这里首先我们用二重循环来做一下#xff0c;发现会时间超时#xff0c;因为这里的时间数是大于10万的#xff0c;所以要么…思路动态规划。
其实这道题和最长递增子序列很像都是以数字为结尾的dp形式也就是把判断条件改了一下就是了。
这里首先我们用二重循环来做一下发现会时间超时因为这里的时间数是大于10万的所以要么就是On)我们需要对dp进行优化操作才行。
为什么要1因为自身也算是一个数我们在dp递推的时候并没有考虑自身的问题所以你可以在初始化dp的时候进行初始化为1也可以最后把数加上1。
首先上二重循环的DP
class Solution {
public:int longestSubsequence(vectorint arr, int difference) {int narr.size();vectorintdp(100100,0);int res0;for(int i0;in;i){for(int j0;ji;j){if(arr[i]-arr[j]difference){dp[i]max(dp[i],dp[j]1);}}resmax(dp[i],res);}return res1;}
};
接下来就是基于对于二重循环的优化了
我们从最长递增子序列的思路中可以知道dp[i]的数组判断的是以arr[i]为尾的最长定差子序列我们的dp下标其实对应的就是arr[i]在arr数组中的位置。换个思路想如果我们直接把arr[i]代表的数放dp的下标会如何呢
假设arr[i]的数表示为v那么dp[v]也就表示了以v为结尾的最长定差子序列的长度了。那么状态转移方程又怎么变化呢由于我们总是在以这个数字为尾况且我们寻找的是它左边的数所以只需要在本数的基础上减去定差就行了也就是对于数组左边的探测了。如果有自然就会1另外会带着这个数字为尾的最长定差子序列就这样一直递推下去。
上代码
class Solution {
public:int longestSubsequence(vectorint arr, int difference) {int narr.size();unordered_mapint,intdp;int res0;for(int i0;in;i){dp[arr[i]]dp[arr[i]-difference]1;resmax(res,dp[arr[i]]);}return res;}
};
