文章目录
- 题目
- 暴力回溯构建等差数组&＃43;数学方法优化
- 以等差数列的最后两元素为状态dp
题目
视频讲解
暴力回溯构建等差数组&＃43;数学方法优化
当出现完全一样元素大小的长度很长的数组数组时&＃xff0c;可计算Cn1…Cnn来实现。
超时&＃xff0c;差最后一个case
class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {using ll &＃61; long long;int n &＃61; nums.size();if(n<3)return 0;auto check &＃61; [&](){int b &＃61; nums[0];for(auto t:nums){if(b!&＃61;t)return false;}return true;};if(check()){ll res &＃61; 1<<n;res -&＃61; n;res -&＃61; n*(n-1)/2;res -&＃61; 1;return res;}int cnt &＃61; 0;function<void(vector<ll>&,int)> backtrack &＃61; [&](vector<ll>&t,int pos){if(t.size()>2)cnt&＃43;&＃43;;for(int i&＃61;pos;i<n;i&＃43;&＃43;){if(t.size()<2){t.emplace_back(nums[i]);backtrack(t,i&＃43;1);t.pop_back();}else{int sz &＃61; t.size();ll gap &＃61; t[sz-1] - t[sz-2];if(gap&＃61;&＃61;(ll)nums[i]-t[sz-1]){t.emplace_back(nums[i]);backtrack(t,i&＃43;1);t.pop_back();}}}};vector<ll>q;backtrack(q,0);return cnt;}
};
以等差数列的最后两元素为状态dp
dp[i][j] 表示以 i 和 j 下标对应最后两元素的等差数列个数&＃xff0c;所以存在转移关系:dp[i][j] &＃43;&＃61; dp[j][k]&＃43;1,(k;
而k是怎么来的呢?
nums[j] - nums[k] &＃61; nums[i] - nums[j] &＃61;> nums[k] &＃61; 2*nums[j]-nums[i]
一旦存在这样的下标 k 便可进行状态转移
class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {using ll &＃61; long long;int n &＃61; nums.size();if(n<3)return 0;unordered_map<ll,vector<int>>check;for(int i&＃61;0;i<nums.size();i&＃43;&＃43;){check[nums[i]].emplace_back(i);}int dp[n][n];int res &＃61; 0;memset(dp,0,sizeof(dp));for(int i&＃61;0;i<n;i&＃43;&＃43;){for(int j&＃61;0;j<i;j&＃43;&＃43;){ll target &＃61; (ll)2*nums[j]-nums[i];vector<int>& t &＃61; check[target];for(auto&& k:t){if(k<j)dp[i][j] &＃43;&＃61; (dp[j][k]&＃43;1);}res &＃43;&＃61; dp[i][j];}}return res;}
};
京公网安备 11010802041100号