最值问题是一种优化问题
最值问题是一种优化问题，比较典型的有
1.最大/最小xx
2.最大/最小xx和
3.最长xx/最长公共xx
4.最大/最小xx路径
这一类问题往往有比较朴素的定义形式, 思考以某个明确而具体的搜索空间里面
以某个 index 为结尾的最值, 它和之前的index的最值的关系是什么?
hc 700.杆子分割
给一个 n 英寸长的杆子和一个包含所有小于 n 的尺寸的价格. 确定通过切割杆并销售碎片可获得的最大值.
样例1 输入：[1, 5, 8, 9, 10, 17, 17, 20] 8 输出：22
解释：
长度 | 1 2 3 4 5 6 7 8
--------------------------------------------
价格 | 1 5 8 9 10 17 17 20
切成长度为 2 和 6 的两段。
样例2 输入：[3, 5, 8, 9, 10, 17, 17, 20] 8 输出：24
解释：
长度 | 1 2 3 4 5 6 7 8
--------------------------------------------
价格 | 3 5 8 9 10 17 17 20
切成长度为 1 的 8 段。
class Solution {
public:
int cutting(vector<int>& prices, int n) {
}
};
300.最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：输入：nums = [0,1,0,3,2,3] 输出：4
示例 3：输入：nums = [7,7,7,7,7,7,7] 输出：1
分析:
1.维护的状态是, 考察以 nums[i] 为结尾的严格递增子序列的长度, 对每个子序列而言, 逐步考察从第一个元素到第 nums[i] 个元素之间的关系
(i). nums[i] 没有比之前的元素更大, 无法实现更大的递增序列 dp[i] = dp[i]
(ii). nums[i] 比之前的元素更大, 可以实现更大的递增序列 dp[i] = dp[j-1] + 1
写出状态转移为
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j-1] + 1);
}
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;
int n = nums.size();
vector<int> dp(n, 1);
int ans = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
}
}
return ans;
}
};
这道题还有二分搜索的方法, 复杂度更低
673.最长递增子序列的个数
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。注意 这个数列必须是 严格 递增的。
示例 1: 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2: 输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
}
};
354.俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。注意：不允许旋转信封。
示例 1：输入：envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出：3 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：输入：envelopes = [[1,1],[1,1],[1,1]] 输出：1
分析:
这个题目是最长递增子序列的二维版本, 如果是一维版本会做了, 我们需要分别处理w和h两个, 想一下先对w和h都排序下, 不妨写个例子
[1,8]
[2,3]
[5,2]
[5,4]
[6,4]
[6,7]
我们可以发现, 因为要求每个维度上面都严格要比前面的数字大才能满足套娃要求, 那么类似[5,2]和[5,4]这种组合, 在对比h这个维度上, 其实需要保证只能算一次2或者4, 这里如果能想到在这种w相同的情况是降序排列h, 然后再对h这个维度进行计算最长上升子序列就实现原有的目的
[1,8]
[2,3]
[5,4]
[5,2]
[6,7]
[6,4]
算下来是 h 取 3,4,7 的时候可以拿到二维的最长上升子序列
[2,3]
[5,4]
[6,7]
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
if (envelopes.empty())
return 0;
int n = envelopes.size();
sort(envelopes.begin(), envelopes.end(), [] (const vector<int>& a, const vector<int>& b) {
if (a[0] == b[0])
return a[1] > b[1];
return a[0] < b[0];
});
vector<int> dp(n, 1);
int ans = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (envelopes[j][1] < envelopes[i][1]) {
dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
}
}
return ans;
}
};
上述代码提交会报超时, 需要用二分继续优化下
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
}
};
53.最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
示例 1：输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：输入：nums = [1] 输出：1
示例 3：输入：nums = [5,4,-1,7,8] 输出：23
分析:
因为数组是有正有负的, 这里定义的状态是, 以 nums[i] 为结尾的最大子数组和为 dp[i], 那么dp [i] 怎么做选择
1.nums[i] 自成一派 dp[i] = nums[i]
2.nums[i] 和之前的数组 dp[i-1] 合并起来, 即 dp[i] = dp[i-1] + nums[i]
状态转移汇总: dp[i] = max(nums[i], dp[i-1] + nums[i])
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len = nums.size();
if (len <= 0) {
return 0;
}
vector<int> dp(len, INT_MIN);
dp[0] = nums[0];
int ans = dp[0];
for (int i = 1; i < len; ++i) {
// dp[i], 表示以 i 为结尾的最大连续子数组和
// 状态转移: 要么是和前面的加起来最大, 要么自成一派最大
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
ans = max(dp[i], ans);
}
return ans;
}
};
1143.最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。示例 1：输入：text1 = “abcde”, text2 = “ace” 输出：3 解释：最长公共子序列是 “ace” ，它的长度为 3 。
示例 2：输入：text1 = “abc”, text2 = “abc” 输出：3 解释：最长公共子序列是 “abc” ，它的长度为 3 。
示例 3：输入：text1 = “abc”, text2 = “def” 输出：0 解释：两个字符串没有公共子序列，返回 0 。
分析:
1.dp[i][j] 表示 t1[0..i-1] 和 t2[0..j-1] 之间的最长公共子序列; 然后做选择的时候无非两种场景
2.确定好 dp[i][j] 所定义的状态, 那么状态发生的选择如下
t1[i-1] == t[j-1], 那么就是 dp[i][j] = dp[i-1][j-1] + 1
t1[i-1] != t[j-1], 那么就是 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
最终我们要的是 dp[m][n]
3.检查边界条件 dp[i][0] 和 dp[0][j], 表示的是长度为i的字符串和长度为 0 的字符串的最长公共子序列长度, 应该设定为 dp[i][0] = 0 && dp[0][j] = 0
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (text1[i-1] == text2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
};
72.编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符示例 1：输入：word1 = “horse”, word2 = “ros” 输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)示例 2：输入：word1 = “intention”, word2 = “execution” 输出：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)
分析:
1.编辑距离的计算方式之间有重叠的结构, 我们考虑动态规划
2.令 dp[i][j] 表示 word1[0..i-1] 和 word2[0..j-1] 的编辑距离
3.想一想边际的情况
比较当前的字符 word[i-1] 和 word[j-1] 如果二者相同, 单词的编辑距离和这两个单词中的这两个相同的字符没关系, 多一个相同字符或者少一个相同的字符不影响编辑距离, 那么状态转移 dp[i][j] = dp[i-1][j-1]
比较当前的字符 word[i-1] 和 word[j-1] 如果二者不相同, 那么想一下可以怎么通过三种方式进行变换, 以及状态转移是什么? 最终的状态转移就是求这三个的最小值; 分析状态转移在这里就是分析这个比较可以由什么操作算过来
(i).对于删除操作来说, dp[i][j], 可以 word1 删除或者 word2 删除一个字符实现, 比如我们比较如下的
s1:applec
s2:apple
当前 word1[i-1] 是第 c, 当前 word2[j-1] 是 e, 我们可以删除 s1 里面的 c , 然后指针向左比较的是 dp[i-1][j]
dp[i][j] = dp[i-1][j] + 1
(ii).对于增加操作来说, dp[i][j], 可以 word1 增加或者 word2 增加一个字符实现
s1:appl
s2:apple
当前 word1[i-1] 是 e, 当前 word2[j-1] 是 l, 我们可以增加 s2 的 e, 然后 word2 指针向左比较的是 dp[i][j-1]
dp[i][j] = dp[i][j-1] + 1
(iii).对于替换来说, 直接将当前字符 word1[i-1] 替换为 word[j-1], 那么可以对 i 和 j 都往前移动一个再比较, 比如如下的例子
s1:appc
s2:appl
把我们比较的是 s1 的 c 和 s2 的 l, 可以把 s1 的 c 替换成 l, 那么 dp[i][j] = dp[i-1][j-1] + 1
4.边界条件 dp[0][j] = j; dp[i][0] = i; 表示一个字符串和另一个空字符串的编辑距离是字符串的长度
class Solution {
public:
int minDistance(string word1, string word2) {
int len1 = word1.size();
int len2 = word2.size();
if (len1 == 0) {
return len2;
}
if (len2 == 0) {
return len1;
}
vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
// 边界条件 单词延伸到第 i 个字符和空字符之间编辑距离 i
for (int i = 0; i <= len1; ++i) {
dp[i][0] = i;
}
for (int i = 0; i <= len2; ++i) {
dp[0][i] = i;
}
for (int i = 1; i <= len1; ++i) {
for (int j = 1; j <= len2; ++j) {
if (word1[i-1] == word2[j-1]) {
// 当前字符相等, 不影响编辑距离
dp[i][j] = dp[i-1][j-1];
} else {
// 当前字符不等, 有3种情况取3者最小值
dp[i][j] = min(min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+1);
}
}
}
return dp[len1][len2];
}
};
712.两个字符串的最小ASCII删除和
给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
示例 1:
输入: s1 = “sea”, s2 = “eat” 输出: 231
解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。
在 “eat” 中删除 “t” 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。示例 2:
输入: s1 = “delete”, s2 = “leet” 输出: 403
解释: 在 “delete” 中删除 “dee” 字符串变成 “let”，
将 100[d]+101[e]+101[e] 加入总和。在 “leet” 中删除 “e” 将 101[e] 加入总和。
结束时，两个字符串都等于 “let”，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 “lee” 或 “eet”，我们会得到 433 或 417 的结果，比答案更大。
分析:
1.这道题和 583 删除字符是一样的, 相比 583 改变是不算最小删除步数, 而是将目标转化为算最小的删除ASCII值, 因此我们修改状态转移的过程
2.dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 删除字符最小ASCII和, 比较当前字符是否相同
3.如果当前字符s1[i-1] == s2[i-1], 那么就不用删除, 继续继承之前的字符最小和dp[i][j] = dp[i-1][j-1]
4.如果当前字符s1[i-1] != s2[i-1], 那么要么删除s1的字符s1[i-1], 即dp[i][j] = dp[i-1][j] + s1[i-1]，要么删除s2[i-1]这个字符, 即dp[i][j] = dp[i][j-1] + s2[j-1]
5.边界条件:
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int m = s1.size();
int n = s2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
}
};
转载请注明来源, from goldandrabbit.github.io
