建筑施工建设网站,官网网站开发,请简述网站制作流程,常州北京网站建设前言#xff1a;本文将简单介绍一下力扣中的几道动态规划习题#xff0c;这些题目可以引入哈希表来保存先前的状态#xff0c;也是一个较好的解题思路 解决动态规划类型题目的核心思想就是把先前的重复的子问题的结果存储#xff0c;在后续的的推导中可以直接获取#xf…前言本文将简单介绍一下力扣中的几道动态规划习题这些题目可以引入哈希表来保存先前的状态也是一个较好的解题思路解决动态规划类型题目的核心思想就是把先前的重复的子问题的结果存储在后续的的推导中可以直接获取无需重复计算。保存结果可以使用一个数组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 位置来寻找符合等差的子序列但是时间复杂度为On* 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){MapInteger,IntegerhashnewHashMap();intret1;for(inta:arr){hash.put(a,hash.getOrDefault(a-difference,0)1);//a - b d,在hash表中寻找是否存在bretMath.max(ret,hash.get(a));//维护最大长度}returnret;}通过上述的方法可以看到以On的时间复杂度进行一次遍历就能得到结果不过此题给定了定长d所以只需要已知一个元素就能推导等差序列后面还有变种题二最长的斐波那契子序列长度题目链接https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/description/解题思路从推导等差数列变为推导斐波那契数列原理相同。假设三个数ab c 构成斐波那契数列则满足a b c 所以要想对斐波那契进行推到需要已知两个数bc才能推出前一个。则 a c - b于是此题目就可以转变为 固定 后两个数查找前面是否存在 元素 a 能构成斐波那契数列即可。固定两个数所以需要创建一个二维dp [i] [j]并且 i j。dp[i][j] 表示 : 以ij位置为末尾的所有子序列中最长的等差序列长度。也就是在题目一中来个双重for循环即可所以问题变为向前寻找a即可寻找的情况如下1 找不到那只需让c 后移即可b继续从[ 0 …i-1]位置进行遍历增大寻找范围2能找到但是a的下标k 有问题假如i k j ,则a就加载bc两数中间值符合位置错误所以不符合3能找到k i j ,此时合法更新dp[i][j] dp[k][i] 1。dp[i][k]是前一个以ab结尾的斐波那契数列长度状态转移这一点需要理清找符合的元素a如何找还需要判断其存在的位置k是否合理不妨我们引入hash存储nums[ ]中的所有元素及其下标映射需要时直接查表即可注意细节1,初始化问题dp[ ][ ]中存储斐波那契数列长度要注意初始化为2便于第一次找到符合的斐波那契数列时正确的长度更新代码参考publicintlenLongestFibSubseq(int[]nums){intnnums.length;int[][]dpnewint[n][n];MapInteger,IntegerhashnewHashMap();for(inti0;in;i){hash.put(nums[i],i);}//初始化把i j的位置初始化也可以全部初始化不过其他位置用不到for(intj0;jn;j){for(inti0;ij;i){dp[i][j]2;}}intmaxLen0;//顺序k i j,a b cfor(intj2;jn;j){for(inti1;ij;i){intanums[j]-nums[i];if(hash.containsKey(a)){//能找到//判断下标kintkhash.get(a);if(kikj)continue;//位置不合法elseif(ki){dp[i][j]dp[k][i]1;//状态转移maxLenMath.max(maxLen,dp[i][j]);}}}}returnmaxLen3?maxLen:0;//不合法返回0}该解法的固定顺序是先固定c,使得b移动去寻找a也可以固定b移动c,寻找a.视情况而定大体逻辑都是利用过去的状态去推导当前的状态而已本文结束如有纰漏还请及时指出~~