算法沉淀——动态规划之子序列问题（下）（leetcode真题剖析）

2024-02-29 04:04
文章标签 leetcode 算法 动态 规划 问题 剖析 真题 序列 之子 沉淀

本文主要是介绍算法沉淀——动态规划之子序列问题（下）（leetcode真题剖析），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

算法沉淀——动态规划之子序列问题

  • 01.最长定差子序列
  • 02.最长的斐波那契子序列的长度
  • 03.最长等差数列
  • 04.等差数列划分 II - 子序列

01.最长定差子序列

题目链接：https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

示例 1：

输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

示例 2：

输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：

输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。

提示：

  • 1 <= arr.length <= 105
  • -104 <= arr[i], difference <= 104

思路

  1. 状态表达： 定义动态规划数组 dp，其中 dp[i] 表示以第 i 个位置的元素为结尾的所有子序列中，最长的等差子序列的长度。
  2. 状态转移方程： 对于 dp[i]，上一个定差子序列的取值定为 arr[i] - difference。只要找到以上一个数为结尾的定差子序列长度的 dp[arr[i] - difference]，然后加上 1，就是以 i 为结尾的定差子序列的长度。这里可以使用哈希表进行优化，将元素和 dp[j] 绑定，放入哈希表中。
  3. 初始化： 刚开始的时候，需要把第一个元素放进哈希表中，即 hash[arr[0]] = 1。
  4. 填表顺序： 根据状态转移方程，填表顺序是从左往右。
  5. 返回值： 根据状态表达，返回整个 dp 数组中的最大值。

代码

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int,int> hash;hash[arr[0]]=1;int ret=1;for(int i=1;i<arr.size();i++){hash[arr[i]]=hash[arr[i]-difference]+1;ret=max(ret,hash[arr[i]]);}return ret;}
};

02.最长的斐波那契子序列的长度

题目链接：https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

  • n >= 3
  • 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

示例 2：

输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。

提示：

  • 3 <= arr.length <= 1000
  • 1 <= arr[i] < arr[i + 1] <= 10^9

思路

  1. 状态表达： 定义动态规划数组 dp，其中 dp[j][i] 表示以第 j 位置以及第 i 位置的元素为结尾的所有的子序列中，最长的斐波那契子序列的长度。
  2. 状态转移方程： 设 nums[j] = b，nums[i] = c，那么这个序列的前一个元素就是 a = c - b。根据 a 的情况讨论：
    • 如果 a 存在，下标为 k，并且 a < b，那么 dp[j][i] = dp[k][j] + 1；
    • 如果 a 存在，但是 b < a < c，那么 dp[j][i] = 2；
    • 如果 a 不存在，那么 dp[j][i] = 2。
  3. 优化点： 在状态转移方程中，需要确定 a 元素的下标，可以在填表之前，将所有的「元素 + 下标」绑定在一起，放到哈希表中。
  4. 初始化： 将表里面的值都初始化为 2。
  5. 填表顺序：
    • 先固定最后一个数；
    • 然后枚举倒数第二个数。
  6. 返回值： 返回 dp 表中的最大值 ret。但是 ret 可能小于 3，小于 3 说明不存在，需要判断一下。

代码

class Solution {
public:int lenLongestFibSubseq(vector<int>& arr) {int n=arr.size();unordered_map<int,int> hash;for(int i=0;i<n;i++) hash[arr[i]]=i;vector<vector<int>> dp(n,vector<int>(n,2));int ret=2;for(int i=2;i<n;++i){for(int j=1;j<i;j++){int x=arr[i]-arr[j];if(x<arr[j]&&hash.count(x))dp[j][i] = dp[hash[x]][j]+1;ret = max(ret,dp[j][i]);}}return ret<3?0:ret;}
};

03.最长等差数列

题目链接：https://leetcode.cn/problems/longest-arithmetic-subsequence/

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：

输入：nums = [3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。

示例 2：

输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。

示例 3：

输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

提示：

  • 2 <= nums.length <= 1000
  • 0 <= nums[i] <= 500

思路

  1. 状态表达： 定义动态规划数组 dp，其中 dp[i][j] 表示以第 i 位置以及第 j 位置的元素为结尾的所有的子序列中，最长的等差序列的长度。
  2. 状态转移方程： 设 nums[i] = b，nums[j] = c，那么这个序列的前一个元素就是 a = 2 * b - c。根据 a 的情况讨论：
    • 如果 a 存在，下标为 k，并且 a < b，那么我们需要以 k 位置以及 i 位置元素为结尾的最长等差序列的长度，然后再加上 j 位置的元素即可。于是 dp[i][j] = dp[k][i] + 1。这里因为会有许多个 k，我们仅需离 i 最近的 k 即可。因此任何最长的都可以以 k 为结尾；
    • 如果 a 存在，但是 b < a < c，那么 dp[i][j] = 2；
    • 如果 a 不存在，那么 dp[i][j] = 2。
  3. 优化点： 在状态转移方程中，需要确定 a 元素的下标。可以一边动态规划，一边保存最近的元素的下标，不用保存下标数组。遍历的时候，先固定倒数第二个数，再遍历倒数第一个数。这样可以在 i 使用完时候，将 nums[i] 扔到哈希表中。
  4. 初始化： 将表里面的值都初始化为 2。
  5. 填表顺序：
    • 先固定倒数第二个数；
    • 然后枚举倒数第一个数。
  6. 返回值： 返回 dp 表中的最大值。

代码

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {unordered_map<int,int> hash;hash[nums[0]]=0;int n=nums.size();vector<vector<int>> dp(n,vector<int>(n,2));int ret=2;for(int i=1;i<n;i++){for(int j=i+1;j<n;j++){int x=2*nums[i]-nums[j];if(hash.count(x)) dp[i][j] = dp[hash[x]][i] + 1;ret=max(ret,dp[i][j]);}hash[nums[i]]=i;}return ret;}
};

04.等差数列划分 II - 子序列

题目链接：https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。

  • 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
  • 再例如，[1, 1, 2, 5, 7] 不是等差序列。

数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。

  • 例如，[2,5,10] 是 [1,2,1,***2***,4,1,***5\***,***10***] 的一个子序列。

题目数据保证答案是一个 32-bit 整数

示例 1：

输入：nums = [2,4,6,8,10]
输出：7
解释：所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

示例 2：

输入：nums = [7,7,7,7,7]
输出：16
解释：数组中的任意子序列都是等差子序列。

提示：

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1

思路

  1. 状态表达： 定义动态规划数组 dp，其中 dp[i][j] 表示以第 i 位置以及第 j 位置的元素为结尾的所有的子序列中，等差子序列的个数。
  2. 状态转移方程： 设 nums[i] = b，nums[j] = c，那么这个序列的前一个元素就是 a = 2 * b - c。根据 a 的情况讨论：
    • 如果 a 存在，下标为 k，并且 a < b，那么以 k 元素以及 i 元素结尾的等差序列的个数为 dp[k][i]，在这些子序列的后面加上 j 位置的元素依旧是等差序列。但是这里会多出来一个以 k, i, j 位置的元素组成的新的等差序列，因此 dp[i][j] += dp[k][i] + 1；
    • 因为 a 可能有很多个，需要全部累加起来。
  3. 优化点： 在状态转移方程中，需要确定 a 元素的下标。因此在 dp 之前，将所有元素和下标数组绑定在一起，放到哈希表中。这里保存下标数组是因为需要统计个数。
  4. 初始化： 刚开始是没有等差数列的，因此初始化 dp 表为 0。
  5. 填表顺序：
    • 先固定倒数第一个数；
    • 然后枚举倒数第二个数。
  6. 返回值： 统计所有的等差子序列，返回 dp 表中所有元素的和。

代码

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n=nums.size();unordered_map<long long,vector<int>> hash;for(int i=0;i<n;i++) hash[nums[i]].push_back(i);vector<vector<int>> dp(n,vector<int>(n));int sum=0;for(int j=2;j<n;j++){for(int i=1;i<j;i++){long long x=(long long)nums[i]*2-nums[j];if(hash.count(x)) for(int& k:hash[x])if(k<i) dp[i][j]+=dp[k][i]+1;sum+=dp[i][j];}}return sum;}
};

这篇关于算法沉淀——动态规划之子序列问题（下）（leetcode真题剖析）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/757524。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2