当前位置：首页 > news >正文

【算法练习】动态规划：哈希表保存状态（一）

news 2026/3/26 22:25:52

前言：本文将简单介绍一下力扣中的几道动态规划习题，这些题目可以引入哈希表来保存先前的状态，也是一个较好的解题思路

解决动态规划类型题目的核心思想就是把先前的重复的子问题的结果存储，在后续的的推导中可以直接获取，无需重复计算。保存结果可以使用一个数组dp[ ]也可以使用hash表

下面就通过几道力扣中的题来初步认识一下该解题思路

一，最长定差子序列

题目链接：

https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/

解题思路

题意不难理解，寻找最长的等差序列即可，这个序列不要求连续，给定了一个差值difference。如果按照以前的做题经验，我们直接创建一个dp[ ]，是否可以解决问题？
我们假定dp[i] 表示为：以i位置为结尾的所有等差子序列中，最长的等差子序列长度

dp[i] 的值，依赖于先前状态的推导，但是dp[]的前驱只保存长度，不能判断当前元素nums[i]是否能和前面的子数组构成等差序列，这样就无法充分利用dp[ ]数组。
虽然可以固定 i ，使得 j 从前往后遍历到 i 位置，来寻找符合等差的子序列，但是时间复杂度为O（n* 2）级别，效率太低会超时

所以本题采用哈希表是更好的选择，哈希表可以达到dp数组同样的效果。我们让hash中存储元素 + 长度。

一个等差序列的核心是差值和一个元素，差值diff方法中已提供，所以我们只要能推导出整个等差序列即可，推导方法很简单
固定 i 位置的元素，向前寻找是否存在符合 nums[i] - nums[j] = diff ,即是否存在等于
nums[i] - diff的元素即可。

所以下面就可以分为三种情况

1：找不到，那让 i ，后移即可，说不定他在后面
2：找得到，那么直接让对应位置的长度值加一即可，和dp[i] = dp[ j] + 1一样。

由于题目要求求最长的等差数组长度，所以子啊维护hash的过程中还要一边更新变量ret

代码参考

publicintlongestSubsequence(int[]arr,intdifference){Map<Integer,Integer>hash=newHashMap<>();intret=1;for(inta:arr){hash.put(a,hash.getOrDefault(a-difference,0)+1);//a - b = d,在hash表中寻找是否存在bret=Math.max(ret,hash.get(a));//维护最大长度}returnret;}

通过上述的方法，可以看到以O（n）的时间复杂度进行一次遍历就能得到结果，不过此题给定了定长d，所以只需要已知一个元素就能推导等差序列，后面还有变种题

二，最长的斐波那契子序列长度

题目链接

https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/description/

解题思路

从推导等差数列变为推导斐波那契数列，原理相同。
假设三个数a，b， c 构成斐波那契数列，则满足：a + b = c ，所以，要想对斐波那契进行推到，需要已知两个数b，c，才能推出前一个。则 a = c - b
于是此题目就可以转变为固定后两个数，查找前面是否存在元素 a 能构成斐波那契数列即可。

固定两个数，所以需要创建一个二维dp [i] [j]并且 i < j。dp[i][j] 表示 : 以i，j位置为末尾的所有子序列中，最长的等差序列长度。也就是在题目一中来个双重for循环即可

所以问题变为向前寻找a即可

寻找的情况如下：

1：找不到，那只需让c 后移即可，b继续从[ 0 …i-1]位置进行遍历，增大寻找范围
2：能找到，但是a的下标k 有问题，假如i < k < j ,则a就加载b，c两数中间，值符合，位置错误，所以不符合
3：能找到，k < i < j ,此时合法，更新dp[i][j] = dp[k][i] + 1。dp[i][k]是前一个以a，b结尾的斐波那契数列长度，状态转移这一点需要理清

找符合的元素a，如何找，还需要判断其存在的位置k是否合理，不妨我们引入hash，存储nums[ ]中的所有元素及其下标映射，需要时直接查表即可

注意细节

1,初始化问题：dp[ ][ ]中存储斐波那契数列长度，要注意初始化为2，便于第一次找到符合的斐波那契数列时正确的长度更新

代码参考

publicintlenLongestFibSubseq(int[]nums){intn=nums.length;int[][]dp=newint[n][n];Map<Integer,Integer>hash=newHashMap<>();for(inti=0;i<n;i++){hash.put(nums[i],i);}//初始化，把i < j的位置初始化，也可以全部初始化，不过其他位置用不到for(intj=0;j<n;j++){for(inti=0;i<j;i++){dp[i][j]=2;}}intmaxLen=0;//顺序：k < i < j,a < b < cfor(intj=2;j<n;j++){for(inti=1;i<j;i++){inta=nums[j]-nums[i];if(hash.containsKey(a)){//能找到//判断下标kintk=hash.get(a);if(k>i&&k<j)continue;//位置不合法elseif(k<i){dp[i][j]=dp[k][i]+1;//状态转移maxLen=Math.max(maxLen,dp[i][j]);}}}}returnmaxLen>=3?maxLen:0;//不合法返回0}