公司海外网站建设,海外营销推广服务,个人公司网站建设答辩,wordpress 首页背景音乐前言
大家好#xff0c;我是jiantaoyab#xff0c;开始刷动态规划的子序列类型相关的题目#xff0c;子序列元素的相对位置和原序列的相对位置是一样的
动态规划5个步骤 状态表示 #xff1a;dp数组中每一个下标对应值的含义是什么dp[i]表示什么状态转移方程#xf…前言
大家好我是jiantaoyab开始刷动态规划的子序列类型相关的题目子序列元素的相对位置和原序列的相对位置是一样的
动态规划5个步骤 状态表示 dp数组中每一个下标对应值的含义是什么dp[i]表示什么状态转移方程 dp[i] 等于什么1 和 2 是动态规划的核心步骤第三步是初始化保证填表的时候不越界填表顺序为了保证填写当前状态的时候所需要的状态已经计算过返回值 最长递增子序列 题目分析 代码
class Solution {
public:int lengthOfLIS(vectorint nums) {int n nums.size();vectorint dp(n, 1);int ret 1;for(int i 1; i n; i){for(int k 0; k i; k){if(nums[k] nums[i])dp[i] max(dp[k] 1, dp[i]);}ret max(ret, dp[i]);}return ret;}
};
摆动序列 代码
class Solution {
public:int wiggleMaxLength(vectorint nums) {int n nums.size();vectorint f(n, 1); vectorint g(n, 1);int ret 1;for(int i 1; i n; i){for(int j 0; j i; j){if(nums[j] nums[i])//递增f[i] max(f[i], g[j] 1); else if(nums[j] nums[i])//递减 g[i] max(g[i], f[j] 1);} ret max(f[i], g[i]);}return ret ;}
};最长递增子序列的个数 题目分析 代码
class Solution {
public:int findNumberOfLIS(vectorint nums) {int n nums.size();vectorint len(n, 1);vectorint count(n, 1);int ret_len 1, ret_count 1;for(int i 1; i n; i){for(int k 0; k i; k){if(nums[k] nums[i]) {if(len[k] 1 len[i]) count[i] count[k];else if(len[k] 1 len[i]){len[i] len[k] 1 ; count[i] count[k];}} }//更新返回值if(ret_len len[i]) ret_count count[i];else if(ret_len len[i]) ret_len len[i], ret_count count[i];}return ret_count;}
};最长数对链 题目分析
dp[i]: 表示以i位置为结尾的最长数对链的长度
在0i-1中取一个j,是数对链的话得满足pairs[j] [1] pairs[i] [0]
代码
class Solution {
public:int findLongestChain(vectorvectorint pairs) {int m pairs.size();vectorint dp (m, 1);sort(pairs.begin(), pairs.end());int ret 1;for(int i 1; i m; i){for(int j 0; j i; j){if(pairs[j][1] pairs[i][0])dp[i] max(dp[j] 1, dp[i]);}ret max(ret, dp[i]);}return ret;}
};最长定差子序列 题目分析 代码
class Solution {
public:int longestSubsequence(vectorint arr, int difference) {int n arr.size();unordered_mapint, int hash; //arr[i], dp[i]int ret 1;//初始化hash[arr[0]] 1;for(int i 1; i n; i){hash[arr[i]] hash[arr[i] - difference] 1;ret max(ret, hash[arr[i]]);}return ret;}
};最长的斐波那契子序列的长度 题目分析 代码
class Solution {
public:int lenLongestFibSubseq(vectorint arr) {int n arr.size();vectorvectorint dp(n, vectorint(n, 2));unordered_mapint, int hash;//将arr中的值和下标绑定起来for(int i 0; i n; i) hash[arr[i]] i;int ret 2;for(int j 2; j n; j) //固定最后一个位置{for(int i 1; i j; i) //固定倒数第二个位置{int x arr[j] - arr[i];if(hash.count(x) x arr[i]) {dp[i][j] dp[hash[x]] [i] 1;ret max(ret, dp[i][j]);}}}return ret 3 ? 0 : ret;}
};最长等差数列 题目分析 代码
class Solution {
public:int longestArithSeqLength(vectorint nums) {int n nums.size();unordered_mapint, int hash; //放nums元素对应的下标hash[nums[0]] 0;int ret 2;vectorvectorint dp(n, vectorint(n, 2));for(int i 1; i n; i) //固定倒数第2个数{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;}
};等差数列划分 II - 子序列 题目分析 代码
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {int n nums.size();unordered_maplong long, vectorint hash; //存放nums元素对应的下标for(int i 0; i n; i) hash[nums[i]].push_back(i); //每个元素的下标可能有多个vectorvectorint dp(n, vectorint(n));int ret 0;for(int j 2; j n; j) //固定最后一个位置{for(int i 1; i j; i) //依次遍历倒数第二个位置{long long x (long long)2 * nums[i] - nums[j];if(hash.count(x)) {//提取出nums[i]的下标for(auto k : hash[x]){if(k i) dp[i][j] dp[k][i] 1;}}ret dp[i][j];}}return ret;}
};
