[C国演义] 第十八章
第十八章
- 最长斐波那契子序列的长度
- 最长等差数列
- 等差序列划分II - 子序列
最长斐波那契子序列的长度
力扣链接
- 子序列 ⇒ dp[i] — —
以 arr[i] 结尾的所有子序列中, 斐波那契子序列的最长长度 - 子序列 ⇒ 状态转移方程 — —
根据最后一个位置的组成来划分
- 初始化 — — 根据状态转移方程, 全都初始化为
2 - 遍历顺序 — — 根据状态转移方程,
从前往后 - 返回结果 — — 返回dp表中的最大值, 记作res; 如果res < 3, 那就返回0, 如果res > 3, 那就返回res
class Solution {
public:int lenLongestFibSubseq(vector<int>& arr) {int n = arr.size();// 建表 + 初始化vector<vector<int>> dp(n, vector<int>(n, 2));// 记录返回结果int res = 2;// 优化unordered_map<int, int> hash; // <数组元素, 下标>for(int i = 0; i < n; i++){hash[arr[i]] = i;}// 填表for(int j = 2; j < n; j++) // 最后一个元素{for(int i = 1; i < j; i++) // 倒数第二个元素{int target = arr[j] - arr[i]; // 第一个元素// 斐波那契数列 -- 递增的if(target < arr[i] && hash.count(target)){dp[i][j] = dp[hash[target]][i] + 1;}res = max(res, dp[i][j]);}}// 返回结果return res < 3 ? 0 : res;}
};
最长等差数列
力扣链接
-
子序列 ⇒ dp[i]的含义:
dp[i]的含义: 以nums[i] 为结尾的所有子序列中, 等差子序列的最长长度 -
子序列 ⇒ 状态转移方程 :
-
初识化 :
都初始化为 2
🗨️dp[0][0] 也 初始化为 2? -
-
遍历顺序 : 根据
优化, 我们采取固定第二个元素, 再枚举最后一个元素的遍历顺序 -
返回结果 :
返回dp表中的最大值
class Solution {
public:int longestArithSeqLength(vector<int>& nums) {int n = nums.size();// 建表 + 初始化vector<vector<int>> dp(n, vector<int>(n, 2));// 优化unordered_map<int, int> hash; // <数组元素, 下标>hash[nums[0]] = 0;int res = 2;// 先固定倒数第二个元素,在枚举最后一个元素 && 边dp边插入hash// -- 有利于找到离i最近的一个targetfor(int i = 1; i < n; i++) // 先固定倒数第二个元素{for(int j = i + 1; j < n; j++) // 枚举最后一个元素{int target = 2 * nums[i] - nums[j]; // 目标的第一个元素if(hash.count(target)) // 如果存在, 更新dp[i][j]{dp[i][j] = dp[hash[target]][i] + 1;}res = max(res, dp[i][j]);}// 依次插入hash表中hash[nums[i]] = i;}return res;}
};
等差序列划分II - 子序列
力扣链接
- 子序列 ⇒ dp[i] :
以nums[i] 为结尾的所有子序列中, 等差子序列的最大数目 - 子序列 ⇒ 状态转移方程 :
根据最后一个位置划分
- 初始化 :
全都初始化为 0 - 遍历顺序 :
根据优化 ⇒ 先固定倒数第二个元素, 再枚举最后一个元素 - 返回结果 :
累加dp表
class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();// 建表 + 初始化vector<vector<int>> dp(n, vector<int>(n, 0));// 优化// 由于前面存在多个target && 我们要全部累加起来// --> 所以, 用一个vector来接收一下下标unordered_map<long long int, vector<int>> hash; // <数组元素, 下标>hash[nums[0]].push_back(0);int res = 0;// 先固定倒数第二个元素,在枚举最后一个元素 && 边dp边插入hashfor(int i = 1; i < n; i++) // 先固定倒数第二个元素{for(int j = i + 1; j < n; j++) // 枚举最后一个元素{long long int target = (long long int ) 2 * nums[i] - nums[j]; // 目标的第一个元素if(hash.count(target)) // 如果存在, 更新dp[i][j]{// 这里的 k 都是在合理区间内的, 全部累加for(auto k : hash[target]){// 全部都累加起来dp[i][j] += dp[k][i] + 1;}}res += dp[i][j];}// 依次插入hash表中hash[nums[i]].push_back(i);}return res;}
};
宣室求贤访逐臣，贾生才调更无伦。
可怜夜半虚前席，不问苍生问鬼神。
— — 李商隐《贾谊》