12306网站的建设历程,知名企业网站人才招聘情况,哪些php网站,郑州网站建设moran第十八章 最长斐波那契子序列的长度最长等差数列等差序列划分II - 子序列 最长斐波那契子序列的长度
力扣链接
子序列 ⇒ dp[i] — — 以 arr[i] 结尾的所有子序列中, 斐波那契子序列的最长长度子序列 ⇒ 状态转移方程 — — 根据最后一个位置的组成来划分 初始化 — — 根… 第十八章 最长斐波那契子序列的长度最长等差数列等差序列划分II - 子序列 最长斐波那契子序列的长度
力扣链接
子序列 ⇒ dp[i] — — 以 arr[i] 结尾的所有子序列中, 斐波那契子序列的最长长度子序列 ⇒ 状态转移方程 — — 根据最后一个位置的组成来划分 初始化 — — 根据状态转移方程, 全都初始化为 2遍历顺序 — — 根据状态转移方程, 从前往后返回结果 — — 返回dp表中的最大值, 记作res; 如果res 3, 那就返回0, 如果res 3, 那就返回res
class Solution {
public:int lenLongestFibSubseq(vectorint arr) {int n arr.size();// 建表 初始化vectorvectorint dp(n, vectorint(n, 2));// 记录返回结果int res 2;// 优化unordered_mapint, 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(vectorint nums) {int n nums.size();// 建表 初始化vectorvectorint dp(n, vectorint(n, 2));// 优化unordered_mapint, 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(vectorint nums) {int n nums.size();// 建表 初始化vectorvectorint dp(n, vectorint(n, 0));// 优化// 由于前面存在多个target 我们要全部累加起来// -- 所以, 用一个vector来接收一下下标unordered_maplong long int, vectorint 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;}
};宣室求贤访逐臣贾生才调更无伦。 可怜夜半虚前席不问苍生问鬼神。 — — 李商隐《贾谊》
