《算法题讲解指南：动态规划算法--子序列问题(附总结)》--32.最长的斐波那契子序列的长度，33.最长等差数列，34.等差数列划分II-子序列

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录32.最长的斐波那契子序列的长度题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析33.最长等差数列题目链接题目描述题目示例解法(动态规划)算法思路C算法代码(解法一)C算法代码(解法二)C算法代码(解法三)算法总结及流程解析34.等差数列划分II-子序列题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析子序列问题总结结束语32.最长的斐波那契子序列的长度题目链接873. 最长的斐波那契子序列的长度 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示对于线性dp我们可以用「经验题目要求」来定义状态表示i.以某个位置为结尾巴拉巴拉;ii.以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示dp[i]表示以i位置元素为结尾的「所有子序列」中最长的斐波那契子数列的长度。但是这里有一个非常致命的问题那就是我们无法确定i结尾的斐波那契序列的样子。这样就会导致我们无法推导状态转移方程因此我们定义的状态表示需要能够确定一个斐波那契序列。根据斐波那契数列的特性我们仅需知道序列里面的最后两个元素就可以确定这个序列的样子。因此我们修改我们的状态表示为dp[i][j]表示以 i 位置以及 j 位置的元素为结尾的所有的子序列中最长的斐波那契子序列的长度。规定一下ij。2.状态转移方程设nums[i]bnums[j]c 那么这个序列的前一个元素就是ac-b。我们根据a的情况讨论i.a存在下标为k并且ab此时我们需要以k位置以及i位置元素为结尾的最长斐波那契子序列的长度然后再加上j位置的元素即可。于是dp[i][j]dp[k][i] 1;ii.a存在但是bac此时只能两个元素自己玩了dp[i][j]2;iii.a不存在此时依旧只能两个元素自己玩了dp[i][j]2。综上状态转移方程分情况讨论即可。优化点我们发现在状态转移方程中我们需要确定a元素的下标。因此我们可以在dp之前将所有的「元素下标」绑定在一起放到哈希表中。3.初始化可以将表里面的值都初始化为2 。4.填表顺序a.先固定最后一个数;b.然后枚举倒数第二个数。5.返回值因为不知道最终结果以谁为结尾因此返回dp表中的最大值ret 。但是ret可能小于3小于3的话说明不存在。因此需要判断一下。C算法代码class Solution { public: int lenLongestFibSubseq(vectorint arr) { int n arr.size(); //将元素和下标进行绑定这样我们计算出元素也就能快速找到对应的位置无需进行遍历查找 unordered_mapint, int hash; for(int i 0; i n; i) { hash[arr[i]] i; } vectorvectorint dp(n, vectorint(n, 2)); //初始化为2的目的是斐波那契构成的最小长度为3后续的加1操作正好可以满足所有情况 int len 2; for(int j 2; j n; j)//固定斐波那契子序列最后一个位置 { for(int i j - 1; i 1; i--)//固定斐波那契倒数第二个位置 { int a arr[j] - arr[i];//获取倒数第三个斐波那契数判断是否存在 if(hash.count(a)) { //我们需要保证a arr[i] arr[j]三者相对位置不能改变 if(a arr[i]) { //因为数组严格递增当i位置时a大于等于arr[i]说明i前面所有情况都是如此 //则三者位置不满足要求无需再往前遍历i了 break; } dp[i][j] dp[hash[a]][i] 1; } len max(len, dp[i][j]); } } return len 2 ? 0 : len; } };算法总结及流程解析33.最长等差数列题目链接1027. 最长等差数列 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示对于线性dp我们可以用「经验题目要求」来定义状态表示i.以某个位置为结尾巴拉巴拉;ii.以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示dp[i]表示以i位置元素为结尾的「所有子序列」中最长的等差序列的长度。但是这里有一个非常致命的问题那就是我们无法确定结尾的等差序列的样子。这样就会导致我们无法推导状态转移方程因此我们定义的状态表示需要能够确定一个等差序列。根据等差序列的特性我们仅需知道序列里面的最后两个元素就可以确定这个序列的样子。因此我们修改我们的状态表示为dp[i][j]表示以 i 位置以及 j 位置的元素为结尾的所有的子序列中最长的等差序列的长度。规定一下ij。2.状态转移方程设nums[i]bnums[j] c 那么这个序列的前一个元素就是a2*b-c。我们根据a的情况讨论a.a存在下标为k并且ab此时我们需要以k位置以及i位置元素为结尾的最长等差序列的长度然后再加上j位置的元素即可。于是dp[i][j]dp[k][i]1 。这里因为会有许多个k我们仅需离i最近的k即可(离i最近的k所表示的dp[k][i]的值一定是大于等于前面的情况)。因此任何最长的都可以以k为结尾;b.a存在但是bac:此时只能两个元素自己玩了dp[i][j]2 ;c.a不存在:此时依旧只能两个元素自己玩了dp[i][j]2。综上状态转移方程分情况讨论即可。优化点我们发现在状态转移方程中我们需要确定a元素的下标。因此我们可以将所有的元素 下标绑定在一起放到哈希表中这里有两种策略a.在dp之前放入哈希表中。这是可以的但是需要将下标形成一个数组放进哈希表中。这样时间复杂度较高而且如果在一开始就将所有元素和下标绑定放入哈希表后续遍历查找是会超时的。但是如果按照下面的b策略一边dp一边保存查找范围就能缩短是可以通过的。b.一边dp一边保存。这种方式我们仅需保存最近的元素的下标不用保存下标数组。但是用这种方法的话我们在遍历顺序那里需要先固定倒数第二个数再遍历倒数第一个数。这样就可以在i 使用完时候将 nums[i]扔到哈希表中。3.初始化:根据实际情况可以将所有位置初始化为2。4.填表顺序:a.先固定倒数第二个数;b.然后枚举倒数第一个数。5.返回值:由于不知道最长的结尾在哪里因此返回dp表中的最大值。C算法代码(解法一)dp[i][j]表示以i和j位置为结尾(ij)所有子序列中最长等差序列的长度先固定最后一个数再枚举倒数第二个数class Solution { public: int longestArithSeqLength(vectorint nums) { //解法一dp[i][j]表示以i和j位置为结尾(ij)所有子序列中最长等差序列的长度 // 先固定最后一个数再枚举倒数第二个数 int n nums.size(); unordered_mapint, vectorint hash; //因为会出现多个相同的数在不同的下标中 //而我们枚举倒数第二个数时需要找到离它最近前一个的倒数第三个数的下标 //如果只用int则可能无法找到枚举当前倒数第二个数离它最近前一个的倒数第三个数的下标 //所以我们需要放在一个数组中存放 hash[nums[0]].push_back(0); vectorvectorint dp(n, vectorint(n, 2)); int len 2; for(int j 1; j n; j) { for(int i 0; i j; i) { int differ nums[j] - nums[i]; int a nums[i] - differ; if(hash.count(a)) { int index -1; for(int in hash[a].size() - 1; in 0; in--) { //找到离i左边最近的a对应的下标 if(hash[a][in] i) { index in; break; } } if(index ! -1) { dp[i][j] dp[hash[a][index]][i] 1; } } len max(len, dp[i][j]); } hash[nums[j]].push_back(j); } return len; } };C算法代码(解法二)dp[i][j]表示以i和j位置为结尾(ij)所有子序列中最长等差序列的长度先固定倒数第二个数再枚举最后一个数class Solution { public: int longestArithSeqLength(vectorint nums) { //解法二dp[i][j]表示以i和j位置为结尾(ij)所有子序列中最长等差序列的长度 // 先固定倒数第二个数再枚举最后一个数 int n nums.size(); unordered_mapint, int hash; //当我们固定倒数第二个数往后枚举最后一个数时 //hash存的倒数第三个数的下标就一定是离倒数第二个数最近的下标(下面代码进行了解释) hash[nums[0]] 0; vectorvectorint dp(n, vectorint(n, 2)); int len 2; for(int i 1; i n; i) { for(int j i 1; j n; j) { int differ nums[j] - nums[i]; int a nums[i] - differ; if(hash.count(a)) { dp[i][j] dp[hash[a]][i] 1; } len max(len, dp[i][j]); } hash[nums[i]] i; //倒数第二个数往后走之前将其元素和下标绑定放入hash中 //这样如果该元素在前面重复出现则下标进行更新 //并且能确定后面当该元素作为倒数第三个数 //更新后的下标一定是在倒数第二个数的前面而且是最近的 } return len; } };C算法代码(解法三)dp[i][j]表示以i位置为结尾且以j为公差所有子序列中最长等差序列的长度class Solution { public: int longestArithSeqLength(vectorint nums) { //解法三dp[i][j]表示以i位置为结尾且以j为公差所有子序列中最长等差序列的长度 int n nums.size(); //因为公差范围-500~500而下标必须0,所以需要进行映射 vectorvectorint dp(n, vectorint(1001, 1)); int len 1; //通过二维中的j表示公差就不需要类似上面两个解法需要两个数才能确定等差序列 //而仅仅一个数也能确定对应的等差序列的样子 //1218 最长定差子数列 就是题目已经给定了公差所以只需要知道一个数(dp[i])就能确定等差序列 //而这道题借助二维的j也就变相类似上面一题的逻辑了 for(int i 1; i n; i)//固定最后一个位置 { for(int j 0; j i; j)//固定倒数第二个位置 { int differ nums[i] - nums[j]; dp[i][differ 500] dp[j][differ 500] 1; //上面可以理解为在公差相同(differ)的情况下 //dp[i] dp[j] 1 (j i) //因为相同公差的情况下最后一个数和倒数第二个数一定是处于同一个等差序列中 //并且因为我们dp初始化为1如果以j位置为结尾公差为differ的等差序列不存在 //1长度为2也能满足只有i、j位置两个数构成等差序列的情况 len max(len, dp[i][differ 500]); } } return len; } };解法三的巧妙之处在于通过[ j ]下标表示公差的值相当于直接将公差进行了确定也就保证了仅需要知道一个数就能确定等差序列的样子了。确定了公差值其实这道题也就类似于前面讲解的1218 最长定差子数列 这道算法题了因为这道算法题就是题目给定了公差值所以一维dp就可以实现而这道题通过二维dp的下标[ j ]来表示公差的值解决思路也就和前面那道题类似了。算法总结及流程解析34.等差数列划分II-子序列题目链接446. 等差数列划分 II - 子序列 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示对于线性dp我们可以用「经验题目要求」来定义状态表示i.以某个位置为结尾巴拉巴拉;ii.以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示dp[i]表示以i位置元素为结尾的「所有子序列」中等差子序列的个数。但是这里有一个非常致命的问题那就是我们无法确定i结尾的等差序列的样子。这样就会导致我们无法推导状态转移方程因此我们定义的状态表示需要能够确定一个等差序列。根据等差序列的特性我们仅需知道序列里面的最后两个元素就可以确定这个序列的样子。因此我们修改我们的状态表示为dp[i][j]表示以 i 位置以及 j 位置的元素为结尾的所有的子序列中等差子序列的个数。规定一下 i j。2.状态转移方程设nums[i]bnums[j]c 那么这个序列的前一个元素就是a 2*b-c 。我们根据a的情况讨论a.a存在下标为k并且ab此时我们知道以k元素以及i元素结尾的等差序列的个数dp[k][i]在这些子序列的后面加上j位置的元素依旧是等差序列。但是这里会多出来一个以 kij 位置的元素组成的新的等差序列因此 dp[i][j] dp[k][i] 1;b.因为a可能有很多个我们需要全部累加起来。综上dp[i][j] dp[k][i] 1 。优化点我们发现在状态转移方程中我们需要确定a元素的下标。因此我们可以在 dp 之前将所有元素下标数组绑定在一起放到哈希表中。这里为何要保存下标数组是因为我们要统计个数所有的下标都需要统计。3.初始化刚开始是没有等差数列的因此初始化dp表为 0 。4.填表顺序a.先固定倒数第一个数;b.然后枚举倒数第二个数。5.返回值我们要统计所有的等差子序列因此返回dp表中所有元素的和。C算法代码class Solution { public: int numberOfArithmeticSlices(vectorint nums) { //解法dp[i][j]表示以i和j位置为结尾(ij)所有子序列中满足等差序列的个数 int n nums.size(); vectorvectorint dp(n, vectorint(n, 0)); unordered_maplong long, vectorint hash; for(int i 0; i n; i) { //因为会出现多个相同的数在不同的下标中 //所以我们需要放在一个数组中存放 hash[nums[i]].push_back(i); } int ret 0; for(int j 2; j n; j)//固定倒数第一个数 { for(int i 1; i j; i)//枚举倒数第二个数 { long long differ (long long)nums[j] - nums[i]; long long a (long long)nums[i] - differ; if(hash.count(a)) { for(int index 0; index hash[a].size(); index) { //dp[i][j]需要将i位置前面所有dp[k][i]的情况全部相加 //因为倒数第三个数下标k可能存在多个位置但是必须保证相加的情况为ki if(hash[a][index] i) { break; } dp[i][j] dp[hash[a][index]][i] 1; } } ret dp[i][j]; } } return ret; } };算法总结及流程解析子序列问题总结结束语到此32.最长的斐波那契子序列的长度33.最长等差数列34.等差数列划分II-子序列 这三道算法题就讲解完了。最长斐波那契子序列使用二维dp记录以i,j为结尾的最长序列长度通过哈希表优化查找最长等差数列提供三种解法其中最优解法利用公差映射将问题转化为类似定差子序列问题等差子序列计数统计所有可能的等差子序列通过哈希表存储元素下标数组。希望大家能有所收获