每日算法刷题Day88:3.12:leetcode 动态规划14道题，用时3h
分享丨【算法题单】动态规划（入门/背包/划分/状态机/区间/状压/数位/树形/优化） - 讨论 - 力扣（LeetCode）
一、0-1背包(二维dp)
1.套路
1.每个物品只能选一次，即要么选，要么不选。所以 0-1 背包是 「选或不选」 的代表。
关于「枚举选哪个」的代表，见本题单的「§4.2 最长递增子序列」。
2.dp[i+1][j]表示nums[0]-nums[i]中和为j的xxx，i:[0,n)，j：[0,target]，dp数组第一维范围：[0,n]，从而转态转移第一维遍历i可以从0开始，dp数组初始化边界dp[0][0]=x
2.题目描述
3.学习经验
1. 416. 分割等和子集(中等,学习)
思想
1.给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
2.能够转换题意为找到一个子集的元素和为总和的一半，即选/不选。
能够注意到动态规划第一维度是数组索引，随着从左到右遍历，状态元素和变了，所以第二维度是元素和。问题是判断，即是/否，所以动态规划数组内容为bool型。
那么 dp[i+1][j]就表示从nums[0]到nums[i](i从0到n-1,dp数组范围0-n)的元素和是否等于j(j从0到总和一半)
递推公式为dp[i+1][j]=dp[i][j-nums[i]] || dp[i][j]
(写成i+1让递归边界dp[0]有意义)
代码
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for (int& x : nums)
sum += x;
if (sum % 2)
return false;
sum /= 2;
vector<vector<bool>> dp(
n + 1,
vector<bool>(
sum + 1,
false)); // dp[i+1][j]表示能否从nums[0]-nums[i]中找到元素和为j的子集
dp[0][0] = true; // 递归边界初始化
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= sum; ++j) {
dp[i + 1][j] = dp[i][j];
if (j >= nums[i])
dp[i + 1][j] = dp[i][j - nums[i]] || dp[i][j];
}
}
return dp[n][sum];
}
};
2.494. 目标和(中等,学习)
思想
1.给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于target的不同 表达式 的数目。
2.学习如何转换成[[二十.动态规划-三.背包#1. 416. 分割等和子集(中等,学习)]]
![[494. 目标和.png]]
3.能够转换题意为找到一个子集的元素和为某个值，即选/不选。
能够注意到动态规划第一维度是数组索引，随着从左到右遍历，状态元素和变了，所以第二维度是元素和。问题是数目，即整形，所以动态规划数组内容为int型。
那么dp[i+1][j]就表示从nums[0]到nums[i](i从0到n-1,dp数组范围0-n)的元素和为j(j从0到目标值)的不同表达式的数目
递推公式为dp[i+1][j]=dp[i][j-nums[i]] || dp[i][j]
(写成i+1让递归边界dp[0]有意义)
代码
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size();
int sum = 0;
for (int& x : nums)
sum += x;
int k = sum - abs(target);
if (k < 0 || k % 2 == 1)
return 0;
k /= 2;
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
dp[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
dp[i + 1][j] = dp[i][j];
if (j - nums[i] >= 0)
dp[i + 1][j] += dp[i][j - nums[i]];
}
}
return dp[n][k];
}
};
3. 2915. 和为目标值的最长子序列的长度(中等,学习初始化)
2915. 和为目标值的最长子序列的长度 - 力扣（LeetCode）
思想
1.给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。
返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。
子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。
2.子序列说明为典型的0/1背包，dp[i+1][j]表示nums[0]-nums[i]中子序列和为j的长度最大值，初始化为不可能，为INT_MIN，而不是-1(因为后面转态转移要+1，-1+1=0变成可达了，但实际上不可达+1仍为不可达)，最终判断是否大于0来决定输出-1还是答案
代码
class Solution {
public:
int lengthOfLongestSubsequence(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> dp(
n + 1,
vector<int>(
target + 1,
INT_MIN)); // dp[i+1][j]表示nums[0]-nums[i]中,子序列和为j的长度最大值,i:[0,n),j:[0,target],初始化为INT_MIN表示不可达
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= target; ++j) {
dp[i + 1][j] = dp[i][j];
if (j >= nums[i])
dp[i + 1][j] = max(dp[i + 1][j],
dp[i][j - nums[i]] + 1); // 不选/选取最大
}
}
if (dp[n][target] < 0) // 判断小于0，而不是INT_MIN，因为会出现INT_MIN+1
return -1;
return dp[n][target];
}
};
二、完全背包(选的状态转移来自当前层)
1.套路
1.物品可以重复选，无个数限制。
2.dp[i+1][j]表示nums[0]-nums[i]，和为j的xxx，不选的状态为dp[i][j]，选的状态为dp[i+1][j-nums[i]]（从当前层i+1，而不是从上一层i，从而允许重复）
2.题目描述
3.学习经验
1. 322. 零钱兑换(中等,学习)
思想
1.给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
2.因为允许重复选，所以为完全背包，相比于0/1背包，选从当前层dp[i+1][j-coins[i]]转移而来（允许重复），而不选的转态是从上一层dp[i][j-coins[i]]转移而来（不允许重复）
代码
1.三维循环，第三维枚举coins[i]取几个
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<vector<int>> dp(
n + 1,
vector<int>(
amount + 1,
INT_MAX /
2)); // dp[i+1][j]表示nums[0]-nums[i]中，凑成总金额为j的最少硬币个数,初始化为INT_MAX/2,放防止下面+k溢出
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= amount; ++j) {
for (int k = 0; k <= j / coins[i]; ++k) { // 多少个coins[i]
dp[i + 1][j] =
min(dp[i + 1][j], dp[i][j - k * coins[i]] + k);
}
}
}
if (dp[n][amount] >= INT_MAX / 2)
return -1;
return dp[n][amount];
}
};
2.二维循环，选的状态从当前层dp[i+1][j-coins[i]]转移而来（允许重复），而不选的转态是从上一层dp[i][j-coins[i]]转移而来（不允许重复）
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<vector<int>> dp(
n + 1,
vector<int>(
amount + 1,
INT_MAX /
2)); // dp[i+1][j]表示nums[0]-nums[i]中，凑成总金额为j的最少硬币个数,初始化为INT_MAX/2,放防止下面+k溢出
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= amount; ++j) {
dp[i + 1][j] = dp[i][j]; // 不选
if (j >= coins[i])
dp[i + 1][j] =
min(dp[i + 1][j],
dp[i + 1][j - coins[i]] + 1); // 从当前层选，可重复
}
}
if (dp[n][amount] >= INT_MAX / 2)
return -1;
return dp[n][amount];
}
};
2. 518. 零钱兑换II(中等)
思想
1.给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
2.dp[i+1][j]表示nums[0]-nums[i]中凑出总金额为j的硬币组合数，初始化为凑不出来0，不影响状态转移。
初始化状态dp[0][0]=1，因为有加法，为了防止溢出，数值类型为unsigned long long
代码
class Solution {
public:
typedef unsigned long long ull;
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<vector<ull>> dp(
n + 1,
vector<ull>(
amount + 1,
0)); // dp[i+1][j]表示nums[0]-nums[i]中，凑出总金额j的组合数
dp[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= amount; ++j) {
dp[i + 1][j] = dp[i][j]; // 不选
if (j >= coins[i])
dp[i + 1][j] += dp[i + 1][j - coins[i]];
}
}
return dp[n][amount];
}
};
3. 279. 完全平方数(中等)
思想
1.给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
2.这题得先求得可重复取的数组nums，从1到(int)sqrt(n)，然后就是完全背包了
代码
class Solution {
public:
typedef long long ll;
int numSquares(int n) {
int maxn = (int)sqrt(n); // maxn*maxn<=n, nums:[1,maxn]
vector<vector<ll>> dp(
maxn + 1,
vector<ll>(
n + 1,
INT_MAX /
2)); // dp[i+1]表示nums[0]-nums[i]中，和为j的最少数量，i:[0,maxn)，j:[0,n]
dp[0][0] = 0;
for (int i = 0; i < maxn; ++i) {
for (int j = 0; j <= n; ++j) {
dp[i + 1][j] = dp[i][j]; // 不选
int tmp = (i + 1) * (i + 1);
if (j >= tmp)
dp[i + 1][j] = min(dp[i + 1][j], dp[i + 1][j - tmp] + 1);
}
}
if (dp[maxn][n] >= INT_MAX / 2)
return 0;
return dp[maxn][n];
}
};
三、多重背包(选做)(第三维度)
1.套路
1.物品可以重复选，有个数限制。
2.dp[i+1][j]表示nums[0]-nums[i]中，和为j的xx。
但是状态转移时，i类型数量有限制，所以需要枚举第三维度k，表示选k个i类型的，要求k<=cnt[i]且j-k*nums[i]>=0，且选的转态转移来自第dp[i]
for(int k=1;k<=min(cnt[i],j/nums[i]);++k){
dp[i+1][j]=dp[i+1][j]+dp[i][j-k*nums[i]];
}
2.题目描述
3.学习经验
1. 2585. 获得分数的方法数(困难,学习)
思想
1.考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分。
返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 109 +7 取余。
注意，同类型题目无法区分。
- 比如说，如果有
3道同类型题目，那么解答第1和第2道题目与解答第1和第3道题目或者第2和第3道题目是相同的。
2.因为每一类有次数限制，所以为多重背包，而不是完全背包，所以要枚举第三维度k，表示选k个i类型的，要求k<=cnt[i]且j-k*mark>=0
代码
class Solution {
public:
typedef long long ll;
const int mod = 1e9 + 7;
int waysToReachTarget(int target, vector<vector<int>>& types) {
int n = types.size();
vector<vector<ll>> dp(
n + 1,
vector<ll>(
target + 1,
0)); // dp[i+1][j]表示type[0]-type[i]中，得到j分的方案数，初始化为0
dp[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= target; ++j) {
dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod; // 不选
// 选，有次数限制，所以再多一维，要求j-k*mark>=0 && k<=cnt
int cnt = types[i][0], mark = types[i][1];
for (int k = 1; k <= min(j / mark, cnt); ++k) {
dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - k * mark]) %
mod; // 从i维度转移
}
}
}
return dp[n][target] % mod;
}
};
四、分组背包(第三维度)
1.套路
1.同一组内的物品至多/恰好选一个。
2.dp[i+1][j]表示nums[0]-nums[i]中，和为j的xx。
但是状态转移时，i类型值有范围，所以需要枚举第三维度k，i类型的范围，要求1<=k<=nums[i](假如题目规定)且j-k>=0，且选的转态转移来自第dp[i]
for(int k=1;k<=min(num[i],j);++k){
dp[i+1][j]=dp[i+1][j]+dp[i][j-k];
}
2.题目描述
3.学习经验
1. 1155. 掷骰子等于目标和的方法数(中等)
1155. 掷骰子等于目标和的方法数 - 力扣（LeetCode）
思想
1.这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果（共有 kn 种方式），使得骰子面朝上的数字总和等于 target。
由于答案可能很大，你需要对 109 + 7 取模。
代码
class Solution {
public:
typedef long long ll;
const int mod = 1e9 + 7;
int numRollsToTarget(int n, int k, int target) {
vector<vector<ll>> dp(
n + 1, vector<ll>(target + 1,
0)); // dp[i+1][j]表示0-i个骰子，和为j的方案数
dp[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= target; ++j) {
for (int t = 1; t <= min(k, j);
++t) { // 第i个骰子值为1-k,要求j>=t
dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - t]) % mod;
}
}
}
return dp[n][target] % mod;
}
};
分享丨【算法题单】动态规划（入门/背包/划分/状态机/区间/状压/数位/树形/优化） - 讨论 - 力扣（LeetCode）
一、最长公共子序列(LCS)
1.套路
1.一般定义 f[i][j] 表示对 (s[:i],t[:j]) 的求解结果。
2.dp[i+1][j+1]表示s[0:i],t[0:j]的xxx，
一般分为s[i]==t[j]时，从dp[i][j]转移
否则，从dp[i+1][j]或dp[i][j+1]转移。
因为可以从左上角，左侧和上侧转移，所以要初始化第0列和第0行(dp数组可以取到n1行,n2列)
for(int i=0;i<=n1;++i) dp[i][0]=i;
for(int j=0;j<=n2;++j) dp[0][j]=j;
2.题目描述
3.学习经验
1. 1143. 最长公共子序列(中等)
思想
1.给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
2.dp[i+1][j+1]表示text1[0:i],text2[0:j]最长公共子序列长度
代码
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n1 = text1.size(), n2 = text2.size();
vector<vector<int>> dp(
n1 + 1,
vector<int>(
n2 + 1,
0)); // dp[i+1][j+1]表示text1[0:i],text2[0:j]最长公共子序列长度
dp[0][0] = 0;
for (int i = 0; i < n1; ++i) {
for (int j = 0; j < n2; ++j) {
if (text1[i] == text2[j]) { // 相等
dp[i + 1][j + 1] = dp[i][j] + 1;
} else { // 不相等
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
}
}
}
return dp[n1][n2];
}
};
2. 583. 两个字符串的删除操作(中等,学习初始化)
583. 两个字符串的删除操作 - 力扣（LeetCode）
思想
1.给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
2.dp[i+1][j+1]表示使word1[0:i]与word2[0:j]相同的最小步数，因为可以从dp[i+1][j]或dp[i][j+1]转移而来，所以要初始化第0行和第0列
代码
class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.size(), n2 = word2.size();
vector<vector<int>> dp(
n1 + 1,
vector<int>(
n2 + 1,
INT_MAX /
2)); // dp[i+1][j+1]表示使word1[0:i]与word2[0:j]相同的最小步数
// 初始化不一样
for (int i = 0; i <= n1; ++i) // 能取到n1
dp[i][0] = i;
for (int j = 0; j <= n2; ++j) // 能取到n2
dp[0][j] = j;
for (int i = 0; i < n1; ++i) {
for (int j = 0; j < n2; ++j) {
if (word1[i] == word2[j]) { // 相等
dp[i + 1][j + 1] = dp[i][j]; // 无需删除
} else { // 不相等
dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j]) + 1;
}
}
}
return dp[n1][n2];
}
};
3. 712. 两个字符串的最小ASCII删除和(中等)
712. 两个字符串的最小ASCII删除和 - 力扣（LeetCode）
思想
1.给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和。
2.跟[[二十一.动态规划-四.经典线性DP#2. 583. 两个字符串的删除操作(中等,学习初始化)]]一样，只不过上提是最小步数，这题是ASCII值的最小和
代码
class Solution {
public:
int get_ascii(char c) { return c - 'a' + 97; }
int minimumDeleteSum(string s1, string s2) {
int n1 = s1.size(), n2 = s2.size();
vector<vector<int>> dp(
n1 + 1,
vector<int>(
n2 + 1,
INT_MAX /
2)); // dp[i+1][j+1]表示使s1[0:i]与s2[0:j]相同的字符ASCII值的最小和
// 初始化不一样
dp[0][0] = 0;
for (int i = 1; i <= n1; ++i) // 能取到n1
dp[i][0] = dp[i - 1][0] + get_ascii(s1[i - 1]);
for (int j = 1; j <= n2; ++j) // 能取到n2
dp[0][j] = dp[0][j - 1] + get_ascii(s2[j - 1]);
for (int i = 0; i < n1; ++i) {
for (int j = 0; j < n2; ++j) {
if (s1[i] == s2[j]) { // 相等
dp[i + 1][j + 1] = dp[i][j]; // 无需删除
} else { // 不相等
dp[i + 1][j + 1] = min(
dp[i][j + 1] + get_ascii(s1[i]),
dp[i + 1][j] + get_ascii(s2[j])); // 删除s1[i]或s2[j]
}
}
}
return dp[n1][n2];
}
};
4. 72. 编辑距离(中等)
思想
1.给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
2.此题相比于[[二十一.动态规划-四.经典线性DP#2. 583. 两个字符串的删除操作(中等,学习初始化)]],多了一个“插入word1一个字符”和“替换word1一个字符”，少了一个“删除word2一个字符”，分析可知“插入word1一个字符”与“删除word2一个字符”等价。所以只需新增“替换word1一个字符”，其状态为dp[i][j]
代码
class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.size(), n2 = word2.size();
vector<vector<int>> dp(
n1 + 1,
vector<int>(
n2 + 1,
INT_MAX /
2)); // dp[i+1][j+1]表示将word1[0:i]转化成word2[0:j]所使用的最少操作数
for (int i = 0; i <= n1; ++i)
dp[i][0] = i;
for (int j = 0; j <= n2; ++j)
dp[0][j] = j;
for (int i = 0; i < n1; ++i) {
for (int j = 0; j < n2; ++j) {
if (word1[i] == word2[j]) {
dp[i + 1][j + 1] = dp[i][j];
} else {
dp[i + 1][j + 1] =
min({dp[i][j + 1], dp[i + 1][j], dp[i][j]}) +
1; // 删除word1[i],删除word2[j](等价于插入word1),替换word1[i]
}
}
}
return dp[n1][n2];
}
};
二、最长递增子序列(LIS)
1.套路
1.做法有很多：
枚举选哪个。（见讲解）
二分。（见讲解）
2.dp数组只需一个维度即可，dp[i]表示以nums[i]结尾的最长严格递增子序列的长度，初始化为1（至少为自己），则还需遍历第二维度j，判断nums[j]<nums[i]，从而状态转移dp[i]=max(dp[i],dp[j]+1)
3.二分方法：g[i]表示长度为i+1的递增子序列的最小可能结尾值
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
vector<int> g; // g[i]表示长度为i+1的递增子序列的最小可能结尾值
for (int& x : nums) {
auto it = lower_bound(g.begin(), g.end(), x); // 找到第一个>=x的位置
if (it - g.begin() + 1 == 3) { // 递增子序列长度存在至少为3
return true;
}
if (it == g.end()) { // 新的递增值
g.push_back(x);
} else { // 替换为更小的值
*it = x;
}
}
return false;
// return g.size(); // 最长递增子序列长度
}
};
2.题目描述
3.学习经验
1. 300. 最长递增子序列(中等,学习)
思想
1.给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
2.dp数组只需一个维度即可，dp[i]表示以nums[i]结尾的最长严格递增子序列的长度，初始化为1（至少为自己），则还需遍历第二维度j，判断nums[j]<nums[i]，从而状态转移dp[i]=max(dp[i],dp[j]+1)
代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(
n,
1); // dp[i]表示以nums[i]结尾的最长严格递增子序列长度,i:[0,n),至少为1
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) { // 满足j<i
if (nums[j] < nums[i]) { // 严格递增
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int res = 0;
for (int i = 0; i < n; ++i)
res = max(res, dp[i]);
return res;
}
};
2.贪心二分:
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> g; // g[i]表示长度为i+1的递增子序列的最小可能结尾值
for (int& x : nums) {
auto it = lower_bound(g.begin(), g.end(), x); // 找到第一个>=x的位置
if (it == g.end()) { // 新的递增值
g.push_back(x);
} else { // 替换为更小的值
*it = x;
}
}
return g.size(); // 最长递增子序列长度
}
};
2. 334. 递增的三元子序列(中等,学习贪心二分)
思想
1.给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
2.可以先求最长递增子序列，最后判断最大值是否大于3(任意值)即可
代码
1.枚举中间(单调栈算法+前缀最小值)[[三.枚举技巧#枚举中间]]
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n = nums.size();
vector<int> right(n,
n); // right[i]表示nums[i]右边第一个比它大的数的下标
vector<int> st;
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && nums[i] >= nums[st.back()])
st.pop_back();
if (!st.empty())
right[i] = st.back();
st.push_back(i);
}
int minn = INT_MAX; // 从左到右遍历最小值
for (int i = 0; i < n; ++i) {
if (minn < nums[i] && right[i] != n)
return true;
minn = min(minn, nums[i]);
}
return false;
}
};
2.可以先求最长递增子序列(得用贪心二分，不然用dp数组会超时)，最后判断最大值是否大于3即可
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
vector<int> g; // g[i]表示长度为i+1的递增子序列的最小可能结尾值
for (int& x : nums) {
auto it = lower_bound(g.begin(), g.end(), x); // 找到第一个>=x的位置
if (it - g.begin() + 1 == 3) { // 递增子序列长度存在至少为3
return true;
}
if (it == g.end()) { // 新的递增值
g.push_back(x);
} else { // 替换为更小的值
*it = x;
}
}
return false;
}
};
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
6
0- 0
已为社区贡献4条内容
所有评论(0)