【C++刷题】优选算法——动态规划第三辑

2024-04-12 08:12
文章标签 算法 动态 规划 c++ 刷题 优选 第三辑

本文主要是介绍【C++刷题】优选算法——动态规划第三辑，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  1. 最大子数组和
状态表示:dp[i]: 表示以i位置元素结尾的所有子数组中的最大和
状态转移方程:dp[i] = max(nums[i], dp[i-1] + nums[i])

int maxSubArray(vector<int>& nums)
{// 1.dp数组vector<int> dp(nums.size());// 2.初始化dp[0] = nums[0];// 3.状态转移方程for(int i = 1; i < dp.size(); ++i){dp[i] = max(nums[i], dp[i-1] + nums[i]);}// 4.返回值int ret = dp[0];for(int i = 1; i < dp.size(); ++i)if(dp[i] > ret) ret = dp[i];return ret;
}
  1. 环形子数组的最大和
通过分类讨论，将环形问题可以转化为线性问题：
第一种情况：最大子数组和处于中间位置
第二种情况：最大子数组和处于两头位置
状态表示:dp_max[i]: 表示以i位置元素结尾的所有子数组中的最大和dp_min[i]: 表示以i位置元素结尾的所有子数组中的最小和
状态转移方程:dp_max[i] = max(nums[i], dp_max[i-1] + nums[i])dp_min[i] = min(nums[i], dp_min[i-1] + nums[i])

int maxSubarraySumCircular(vector<int>& nums)
{// 1.dp数组vector<int> dp_max(nums.size());vector<int> dp_min(nums.size());// 2.初始化dp_max[0] = dp_min[0] = nums[0];// 3.状态转移方程for(int i = 1; i < nums.size(); ++i){dp_max[i] = max(nums[i], dp_max[i-1] + nums[i]);dp_min[i] = min(nums[i], dp_min[i-1] + nums[i]);}// 4.返回值int sum = 0;for(int i = 0; i < nums.size(); ++i){sum += nums[i];}int max = dp_max[0];int min = dp_min[0];for(int i = 1; i < nums.size(); ++i){if(dp_max[i] > max) max = dp_max[i];if(dp_min[i] < min) min = dp_min[i];}// if(sum - min == 0) return max;// return max > sum - min ? max : sum - min;return sum == min ? max : std::max(max, sum - min);
}
  1. 乘积最大子数组
状态表示:f[i]: 表示以i位置元素结尾的所有子数组中最大积的值g[i]: 表示以i位置元素结尾的所有子数组中最小积的值
状态转移方程:f[i] = max(nums[i], max(f[i-1] * nums[i], g[i-1] * nums[i]));g[i] = min(nums[i], min(f[i-1] * nums[i], g[i-1] * nums[i]));

int maxProduct(vector<int>& nums)
{// 1.dp数组vector<int> f(nums.size());vector<int> g(nums.size());// 2.初始化f[0] = g[0] = nums[0];// 3.状态转移方程for(int i = 1; i < nums.size(); ++i){f[i] = max(nums[i], max(f[i-1] * nums[i], g[i-1] * nums[i]));g[i] = min(nums[i], min(f[i-1] * nums[i], g[i-1] * nums[i]));}// 4.返回值int ret = f[0];for(int i = 1; i < f.size(); ++i){if(f[i] > ret) ret = f[i];}return ret;
}
  1. 乘积为正数的最长子数组长度
状态表示:f[i]: 表示以i位置元素结尾的所有子数组中乘积为正的最大的子数组长度g[i]: 表示以i位置元素结尾的所有子数组中乘积为负的最大的子数组长度

int getMaxLen(vector<int>& nums)
{// 1.dp数组vector<int> f(nums.size());vector<int> g(nums.size());// 2.初始化f[0] = (nums[0] > 0 ? 1 : 0);g[0] = (nums[0] < 0 ? 1 : 0);// 3.状态转移方程for(int i = 1; i < nums.size(); ++i){if(nums[i] > 0) {f[i] = f[i-1] + 1;g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;}else if(nums[i] < 0){f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;g[i] = f[i-1] + 1;}}// 4. 返回值int ret = f[0];for(int i = 1; i < f.size(); ++i){if(f[i] > ret) ret = f[i];}return ret;
}
  1. 等差数列划分
状态表示:dp[i]: 表示以i位置元素结尾的所有子数组中等差数列的个数
状态转移方程:nums[i] - nums[i-1] == nums[i-1] - nums[i-2] 情况下: dp[i] = dp[i-1] + 1;否则: dp[i] = 0;

int numberOfArithmeticSlices(vector<int>& nums)
{// 0.边界情况处理if(nums.size() < 3) return 0;// 1.dp数组vector<int> dp(nums.size());// 2.初始化dp[0] = dp[1] = 0;// 3.状态转移方程for(int i = 2; i < dp.size(); ++i){if(nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]){dp[i] = dp[i-1] + 1;}}// 4.返回值int ret = 0;for(int i = 0; i < dp.size(); ++i){ret += dp[i];}return ret;
}
  1. 最长湍流子数组
状态表示:f[i]: 表示以i位置元素为结尾的所有子数组中，最后呈现"上升"状态的最长湍流数组的长度g[i]: 表示以i位置元素为结尾的所有子数组中，最后呈现"下降"状态的最长湍流数组的长度
状态转移方程:if(arr[i-1] > arr[i]) f[i] = g[i-1] + 1;else f[i] = 1;if(arr[i-1] < arr[i]) g[i] = f[i-1] + 1;else g[i] = 1;

int maxTurbulenceSize(vector<int>& arr)
{// 1.dp数组vector<int> f(arr.size());vector<int> g(arr.size());// 2.初始化f[0] = g[0] = 1;// 3.状态转移方程for(int i = 1; i < arr.size(); ++i){if(arr[i-1] > arr[i]){f[i] = g[i-1] + 1;}else{f[i] = 1;}if(arr[i-1] < arr[i]){g[i] = f[i-1] + 1;}else{g[i] = 1;}}// 4.返回值int ret = 0;for(int i = 0; i < arr.size(); ++i){if(f[i] > ret) ret = f[i];if(g[i] > ret) ret = g[i];}return ret;
}
  1. 单词拆分
状态表示:dp[i]: 表示[0, i]区间内的字符串，能否被字典中的单词拼接而成
状态转移方程:dp[i] = dp[j-1] == true && s(j ~ i) in the wordDict

bool Find(string s, vector<string>& wordDict)
{for(auto &e : wordDict){if(s == e) return true;}return false;
}
bool wordBreak(string s, vector<string>& wordDict)
{// 1.dp数组vector<bool> dp(s.size());// 2.初始化dp[0] = Find(s.substr(0, 1), wordDict);// 3.状态转移方程for(int i = 1; i < dp.size(); ++i){bool flag = false;            int j = i;for(; j >= 0; --j){if(dp[j] && Find(s.substr(j + 1, i - j), wordDict)){flag = true;break;}}if(j < 0 && Find(s.substr(0, i + 1), wordDict)) flag = true;dp[i] = flag;}// 4.返回值return dp.back();
}
  1. 环绕字符串中唯一的子字符串
状态表示:dp[i]: 表示以i位置元素为结尾的所有的子串中，在base中出现的次数
状态转移方程:s[i-1] + 1 == s[i] || (s[i-1] == 'z' && s[i] == 'a') -> dp[i] = dp[i-1] + 1;else -> dp[i] = 1;

int findSubstringInWraproundString(string s)
{// 1.dp数组vector<int> dp(s.size());// 2.初始化dp[0] = 1;// 3.状态转移方程for(int i = 1; i < dp.size(); ++i){if(s[i-1] + 1 == s[i] || (s[i-1] == 'z' && s[i] == 'a')){dp[i] = dp[i-1] + 1;}else{dp[i] = 1;}}// 4.返回值vector<int> v(26);for(int i = 0; i < dp.size(); ++i){v[s[i] - 'a'] = max(dp[i], v[s[i] - 'a']);}int sum = 0;for(int i = 0; i < 26; ++i){sum += v[i];}return sum;
}
  1. 最长递增子序列
状态表示:dp[i]: 表示以i位置元素为结尾的所有子序列中，最长递增子序列的长度
状态转移方程:nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1);

int lengthOfLIS(vector<int>& nums)
{// 1.dp数组vector<int> dp(nums.size(), 1);// 2.初始化// 3.状态转移方程for(int i = 1; i < dp.size(); ++i){for(int j = i - 1; j >= 0; --j){if(nums[i] > nums[j]){dp[i] = max(dp[i], dp[j] + 1);}}}// 4.返回值int ret = 0;for(int i = 0; i < dp.size(); ++i){ret = max(ret, dp[i]);}return ret;
}
  1. 摆动序列
状态表示:dp[i]: 表示以i位置元素为结尾的所有子序列中，最长摆动序列的长度继续细化:f[i]: 表示以i位置元素为结尾的所有子序列中，最后一个位置呈现"上升"趋势的，最长摆动序列的长度g[i]: 表示以i位置元素为结尾的所有子序列中，最后一个位置呈现"下降"趋势的，最长摆动序列的长度
状态转移方程:nums[j] < nums[i]: f[i] = max(g[j] + 1, f[i]);nums[j] < nums[i]: g[i] = max(f[j] + 1, g[i]);

int wiggleMaxLength(vector<int>& nums)
{// 1.dp数组vector<int> f(nums.size(), 1);vector<int> g(nums.size(), 1);// 2.初始化// f[0] = g[0] = 1;// 3.状态转移方程for(int i = 1; i < nums.size(); ++i){for(int j = i - 1; j >= 0; --j){if(nums[j] < nums[i]){f[i] = max(g[j] + 1, f[i]);}else if(nums[j] > nums[i]){g[i] = max(f[j] + 1, g[i]);}}}// 4.返回值int f_max = 0, g_max = 0;for(int i = 0; i < nums.size(); ++i){f_max = max(f_max, f[i]);g_max = max(g_max, g[i]);}return max(f_max, g_max);
}
  1. 最长递增子序列的个数
状态表示:len[i]: 表示以i位置元素为结尾的所有子序列中，最长递增子序列的“长度”count[i]: 表示以i位置元素为结尾的所有子序列中，最长递增子序列的“个数”
状态转移方程:nums[j] < nums[i]:len[j] + 1 == len[i]:cnt += count[j];len[j] + 1 > len[i]:len[i] = len[j] + 1;cnt = count[j];

int findNumberOfLIS(vector<int>& nums)
{// 1.dp数组vector<int> len(nums.size(), 1);vector<int> count(nums.size(), 1);// 2.初始化// len[0] = 1;// count[0] = 1;// 3.状态转移方程for(int i = 1; i < nums.size(); ++i){int cnt = 1;for(int j = i - 1; j >= 0; --j){if(nums[j] < nums[i]){if(len[j] + 1 == len[i]) cnt += count[j];else if(len[j] + 1 > len[i]){len[i] = len[j] + 1;cnt = count[j];}}}count[i] = cnt;}// 4.返回值int max_len = 1;int cnt = 0;for(int i = 0; i < nums.size(); ++i){if(len[i] == max_len) cnt += count[i];else if(len[i] > max_len){max_len = len[i];cnt = count[i];}}return cnt;
}
  1. 最长数对链
状态表示:dp[i]表示: 以i位置元素为结尾的所有数对链中，最长的数对链的长度
状态转移方程:pairs[j][1] < pairs[i][0]:dp[i] = max(dp[i], dp[j] + 1);

int findLongestChain(vector<vector<int>>& pairs)
{// 0.预处理sort(pairs.begin(), pairs.end());// 1.dp数组vector<int> dp(pairs.size(), 1);// 2.初始化// dp[0] = 1;// 3.状态转移方程for(int i = 1; i < dp.size(); ++i){for(int j = i - 1; j >= 0; --j){if(pairs[j][1] < pairs[i][0]){dp[i] = max(dp[i], dp[j] + 1);}}}// 4.返回值int ret = dp[0];for(int i = 1; i < dp.size(); ++i){ret = max(ret, dp[i]);}return ret;
}
  1. 最长定差子序列
状态表示:dp[i]: 表示以i位置元素为结尾的所有子序列中，最长的等差子序列的长度
状态转移方程:hash[arr[i]] = hash[arr[i] - difference] + 1;

int longestSubsequence(vector<int>& arr, int difference)
{// 1.dp数组unordered_map<int, int> hash; // <arr[i], dp[i]>// 2.初始化hash[arr[0]] = 1;// 3.状态转移方程for(int i = 1; i < arr.size(); ++i){if(hash.count(arr[i] - difference)){hash[arr[i]] = hash[arr[i] - difference] + 1;}else{hash[arr[i]] = 1;}}// 4.返回值int ret = 0;for(auto &e : hash){ret = max(ret, e.second);}return ret;
}
  1. 最长的斐波那契子序列的长度
状态表示:dp[i][j]: 表示以i位置元素以及j位置元素为结尾的所有子序列中，最长的斐波那契子序列的长度 (i < j)
状态转移方程:vv[i][j] = vv[hash[arr[j] - arr[i]]][i] + 1;

int lenLongestFibSubseq(vector<int>& arr)
{unordered_map<int, int> hash; // <arr[i], i>for(int i = 0; i < arr.size(); ++i){hash[arr[i]] = i;}// 1.dp数组vector<vector<int>> vv(arr.size(), vector<int>(arr.size(), 2));// 2.初始化// 3.状态转移方程   for(int j = 2; j < vv[0].size(); ++j){for(int i = 1; i < j; ++i){if(hash.count(arr[j] - arr[i]) && hash[arr[j] - arr[i]] < i){vv[i][j] = vv[hash[arr[j] - arr[i]]][i] + 1;}}}// 4.返回值int ret = 2;for(int j = 2; j < vv[0].size(); ++j){for(int i = 1; i < j; ++i){ret = max(ret, vv[i][j]);}}return ret < 3 ? 0 : ret;
}
  1. 最长等差数列
状态表示:dp[i][j]: 表示以i位置元素以及j位置元素为结尾的所有子序列中，最长的等差子序列的长度
状态转移方程:hash.count(elem): dp[i][j] = dp[hash[elem]][i] + 1;

int longestArithSeqLength(vector<int>& nums)
{if(nums.size() == 2) return 2;// 0.优化unordered_map<int, int> hash; // <nums[i], i>hash[nums[0]] = 0;// 1.dp数组vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 2));// 2.初始化// 3.状态转移方程for(int i = 1; i < nums.size() - 1; ++i){for(int j = i + 1; j < nums.size(); ++j){int a = 2 * nums[i] - nums[j];if(hash.count(a)){dp[i][j] = dp[hash[a]][i] + 1; }}hash[nums[i]] = i;}// 4.返回值int ret = 0;for(int i = 1; i < nums.size() - 1; ++i){for(int j = i + 1; j < nums.size(); ++j){ret = max(ret, dp[i][j]);}}return ret;
}
  1. 等差数列划分 II - 子序列
状态表示:dp[i][j]: 表示以i位置元素以及j位置元素为结尾的所有子序列中，所有等差子序列的个数
状态转移方程:nums[k] == (long long)2 * nums[i] - nums[j]: dp[i][j] += (dp[k][i] + 1);

int numberOfArithmeticSlices(vector<int>& nums)
{// 1.dp数组vector<vector<int>> dp(nums.size(), vector<int>(nums.size()));// 2.初始化// 3.状态转移方程for(int i = 1; i < nums.size() - 1; ++i){for(int j = i + 1; j < nums.size(); ++j){for(int k = i - 1; k >= 0; --k){if(nums[k] == (long long)2 * nums[i] - nums[j]){dp[i][j] += (dp[k][i] + 1);}}}}// 4.返回值int ret = 0;for(int i = 1; i < nums.size() - 1; ++i){for(int j = i + 1; j < nums.size(); ++j){ret += dp[i][j];}}return ret;
}

这篇关于【C++刷题】优选算法——动态规划第三辑的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

Windows下C++使用SQLitede的操作过程

Windows下C++使用SQLitede的操作过程

《Windows下C++使用SQLitede的操作过程》本文介绍了Windows下C++使用SQLite的安装配置、CppSQLite库封装优势、核心功能（如数据库连接、事务管理）、跨平台支持及性能优... 目录Windows下C++使用SQLite1、安装2、代码示例CppSQLite：C++轻松操作SQ
阅读更多...
C++中RAII资源获取即初始化

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操
阅读更多...
C++中零拷贝的多种实现方式

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri
阅读更多...
C++高效内存池实现减少动态分配开销的解决方案

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现：TCMalloc与Jemalloc1. TCM
阅读更多...
C++ 函数 strftime 和时间格式示例详解

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五
阅读更多...
C++作用域和标识符查找规则详解

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域（Scope）和标识符查找（IdentifierLookup）是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找（Ordinary Lookup）2. 限定查找（Qualif
阅读更多...
Java调用C#动态库的三种方法详解

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢？今天,我们... 目录方法1：C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1：创建C#类库（.NET
阅读更多...
MyBatis编写嵌套子查询的动态SQL实践详解

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可
阅读更多...
C/C++ chrono简单使用场景示例详解

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》：本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示
阅读更多...
C++/类与对象/默认成员函数@构造函数的用法

C++/类与对象/默认成员函数@构造函数的用法

《C++/类与对象/默认成员函数@构造函数的用法》：本文主要介绍C++/类与对象/默认成员函数@构造函数的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录名词概念默认成员函数构造函数概念函数特征显示构造函数隐式构造函数总结名词概念默认构造函数：不用传参就可以
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2