上面是一个按照时间段发生的任务a,b,c,d,e,f,g,h
,有的任务之间会有时间重叠。定义:
j
开始于时间s_j , 结束时间为f_j 目标:对于每个任务的权重都看作一样的,都一样重要。此时从上述任务中找到最多能互相兼容的任务集合。
从上面可以看到,兼容最多的任务集合是{b, e, h}
解决办法:贪心算法
贪心算法总是每一步做出当前最优的选择,贪心算法并不总能得到最优解,但是它是最简单最容易实现的算法。
无权区间调度问题贪心算法:
先将任务以某种顺序排序,再按顺序挑选互相兼容的任务。越早完成一个任务就能去完成下一个任务。这样就能尽可能多的完成任务
对于以上三种情况:
e,a,b,c,d
但是可以看到,a,b,c,d
都与e
时间段都存在重叠,最终结果是e
,但最优解是a,b,c,d
,四个任务时间段没有重叠部分c,b,a
,但是可以看到,a,b
都与c
时间段存在重叠,最终结果是c
,但最优解是a, b
,两任务时间段没有重叠部分f, d, a, b, c, e, g, ...
,最终结果是f, a, d
, 但最优解是a,b,c,d
,四个任务时间段没有重叠部分正确的排序策略是按照结束时间排序:
时间排序的复杂度是O(nlogn)
证明:
假设上面是贪心算法,下面是最优解。r
时刻以前的两序列一样,下面选择第r+1
时刻,如何选取呢?
贪心算法的选取规则就是选择结束时间最早的那个任务,但是其开始时间会比第r
时刻的结束时间要晚,这样才不会冲突,然后越早完成任务才能越早去完成下一个任务。
上面是一个按照时间段发生的任务a,b,c,d,e,f,g,h
,有的任务之间会有时间重叠。定义:
j
开始于时间s_j , 结束时间为f_j 目标:对于每个任务的权重并不一样,有的任务重要,权重更高一些。此时从上述任务中找到权重最大且互相兼容的任务集合。
带权区间调度问题与不带权调度问题的区别是任务的重要性不一样,不能按照之前的贪心算法按照最后结束时间排序:
比如上面的a,b
两个任务,如果按照贪心算法根据结束时间最早的话,应该选择a
任务,但a
任务的权重仅为1,而任务b
权重为999,因此应该选择b
任务
那么对于带权区间调度问题应该怎么处理呢?答案是动态规划
解题思路:动态规划
先将任务按照结束时间排序:
定义状态OPT(j)
为任务{1,2,3...,j}
的最大权重,那么可以得到:
定义p(j)
为结束时间离j
的开始时间最近的任务,如P(8)=5, p(7)=3, p(6)=2, P(5)=0, P(4)=1, P(3)=0, p(2)=0, p(1)=0
,二者不重叠的任务
OPT(j)
的值有两种情况:
j
,则OPT(j) = v_j + OPT(P(j)) 完整的状态转移方程为:
对于上述举例,最优解是OPT(8),但是由于计算OPT(8)需要计算OPT(7),所以计算顺序为OPT(1),OPT(2),...,OPT(8)
假如一个问题的状态转移方程为max(v_j + OPT(P(j)), OPT(j+1))
, 则需要先计算OPT(m), OPT(m-1)..., m
是虚列中索引最大的元素
从0开始往n计算,m[0]->m[1]->m[2]...->m[n]
输入n
个任务,s
是开始时间,f
是结束时间,v
是任务的权重
P(j)
, 即找到每个任务前面最近的不重叠的任务排序时间复杂度为O(nlogn) 找P(j)
时间复杂度为O(n) : 采用双指针,按照开始时间排序一次,按照结束时间排序一次,左指针指向开始时间排序的结束,右指针指向结束时间排序的结束时间,左右开始遍历
维护两个指针,一个指针遍历开始时间序列,一个指针遍历结束时间序列,左指针是起始时间,右指针是结束时间,对于任务8而言,left是8,right是11,right--
往上遍历找到结束时间小于left的任务,可以看到任务5的结束时间是小于left的,因此P(8)=5
;此时left指针--
,到达任务7,由于任务5的结束时间是大于任务7的开始时间,右指针right继续上移right--
,直到任务3,因此P(7)=3
,以此类推
空间复杂度为O(n)
使用递归的方式去完成
小偷偷东西,但是背包的重量或者体积受限,如何才能使得偷到的东西总价值最多
j
重量为w_j>0 和价值v_j>0W
目标:使得背包物品总价值最大
贪心算法行不通:
如果只是一个限制条件的话,贪心算法是可行的。如果是两个及以上的限制的话,还是要考虑动态规划方法
定义OPT(i)
是物品1,2,...,i放入背包后的最大价值,那么有下面两种情况
i
,OPT(i) = OPT(i-1) i
,OPT(i) = OPT(i-1) 上述状态方程没有考虑到放入物品后,除了价值增加之外,背包的能够再放入的重量也要减去该物品的重量
因此定义定义OPT(i, w)
是物品1,2,...,i放入容量为w
背包后的最大价值,那么有下面两种情况
i
,OPT(i, w) = OPT(i-1, w) i
,OPT(i, w^‘) = v_i + OPT(i-1, w-w_i) i=0
,OPT(i, w) = 0 w_i > w
, OPT(i, w) = OPT(i-1, w) 如果物体的重量超过背包能容许放入的重量,那么该物体将不会放入
因此最终的状态转移方程为:
根据w
由小到大,i
由小到大计算
自底向上
基于上面的表可以得到,当w限制为11时候,最优解是拿取商品3和4,总价值是40,总重量是11,满足要求
自顶向下
使用递归的方式,有些地方不需要进行计算
贪心算法和动态规划算法是比较巧妙的算法,需要挖掘一些限制条件和状态变换规律
给你一个整数数组 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
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶: 如果你已经实现复杂度为 O(n)
的解法,尝试使用更为精妙的 分治法 求解。
解题思路
OPT(i)
代表以第i
个数结尾的连续子数组的最大和,则有OPT(0)=-2, OPT(1)=1, OPT(2)=-2, OPT(3)=4, OPT(4)=3, OPT(5)=5, OPT(6)=6, OPT(7)=1, OPT(8)=5
采用动态规划方法:
OPT(i)
代表以第i
个数结尾的连续子数组的最大和代码实现
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return None
n = len(nums)
opt = [nums[0]] * n
for i in range(1, n):
opt[i] = max(nums[i], nums[i]+opt[i-1])
return max(opt)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector <int> dp(n+1, 0);
for(int i=0; i<n; i++)
{
dp[i+1] = max(dp[i]+nums[i], nums[i]);
}
int maxNum = INT_MIN;
for(int i=1; i<=n; i++)
{
maxNum = max(maxNum, dp[i]);
}
return maxNum;
}
};
这里有dp空间可以优化的地方,因为只与前面那个有关系,可以用一个变量来保存该值
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0;
int maxAns = nums[0];
for(const auto &x: nums)
{
pre = max(pre+x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
给定两个字符串 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 <= text1.length, text2.length <= 1000
text1
和 text2
仅由小写英文字符组成。解题思路:
OPT(i, j)
代表字符串t1[0:i]
和字符串t2[0:j]
的最长公共子序列的长度动态规划:
OPT(i, j)
代表字符串t1[0:i]
和字符串t2[0:j]
的最长公共子序列的长度OPT(i, j) = OPT(i-1, j-1) + 1
OPT(i, j) = max(OPT(i-1, j), OPT(i, j-1))
OPT(0, j) = OPT(i, 0) = 0
初始化行与列OPT(i, j) = OPT(i-1, j-1) + 1
if t_1[i] == t_2[j] else OPT(i, j) = max(OPT(i-1, j), OPT(i, j-1))
i,j
从小到大计算=
代码实现
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
len1 = len(text1) # 行
len2 = len(text2) # 列
dp = [[0] * (len2+1) for _ in range(len1+1)] # 多加一行一列,赋值为0
for i in range(len1):
for j in range(len2):
if text1[i] == text2[j]:
dp[i+1][j+1] = dp[i][j] + 1 # i从0开始,但是元素是从下标1开始
else:
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
return dp[-1][-1]
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.size();
int len2 = text2.size();
vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
for(int i=0; i<len1; i++)
{
for(int j=0; j<len2; 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[len1][len2];
}
};
时间复杂度:O(mn) , m,n
分别为两字符串的长度
空间复杂度:O(mn)
给定一个数组 prices
,它的第 i
个元素 prices[i]
表示一支给定股票第 i
天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0
。
示例 1:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
提示:
1 <= prices.length <= 105
0 <= prices[i] <= 104
解题思路:
i<j
的情况下,找max(prices[j]-prices[i])
dp[i]
表示前i
天的最小值i+1
天的价格减去前i
天的最小值就是利润。并更新最小值prices[0]
代码实现
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n < 2:
return 0
dp = [0] * n
dp[0] = prices[0]
res = 0
for i in range(1, n):
res = max(res, prices[i]-dp[i-1])
dp[i] = min(dp[i-1], prices[i])
return res
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n < 2)
{
return 0;
}
vector<int> dp(n, 0);
dp[0] = prices[0];
int res = 0;
for(int i=1; i<n; i++)
{
res = max(res, prices[i]-dp[i-1]);
dp[i] = min(dp[i-1], prices[i]);
}
return res;
}
};
由于dp的状态转移方程只与前一个相关,这里可以优化其空间,只用一个变量进行保存即可;
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n < 2)
{
return 0;
}
int min_val = prices[0];
int res = 0;
for(int i=1; i<n; i++)
{
res = max(res, prices[i]-min_val);
min_val = min(min_val, prices[i]);
}
return res;
}
};
时间复杂度:O(n)
空间复杂度:O(1)
给定一个数组 prices
,其中 prices[i]
表示股票第 i
天的价格。
在每一天,你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它,然后在 同一天 出售。返回 你能获得的 最大 利润 。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示:
解题思路:
不购买
购买
dp[i][0]
表示第i
天手里无股票的利润, dp[i][1]
表示第i
天手里有一支股票的利润代码实现:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n < 2:
return 0
dp = [[0] * 2 for _ in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
return dp[n-1][0] # 手里无股票的时候利润肯定是最大的
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n<2)
{
return 0;
}
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i=1; i<n; i++)
{
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);
}
return dp[n-1][0];
}
};
由于dp的关系只与前一项有关系,可以对空间进行优化,使用两个变量来代替二维数组存储相应的结果;
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n<2)
{
return 0;
}
int not_buy_cost = 0;
int buy_cost = -prices[0];
for(int i=1; i<n; i++)
{
not_buy_cost = max(not_buy_cost, buy_cost+prices[i]);
buy_cost = max(buy_cost, not_buy_cost-prices[i]);
}
return not_buy_cost;
}
};
时间复杂度:O(n)
空间复杂度:O(1)
给你一个字符串 s
,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
示例 1:
输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。
示例 2:
输入:s = "cbbd"
输出:2
解释:一个可能的最长回文子序列为 "bb" 。
提示:
1 <= s.length <= 1000
s
仅由小写英文字母组成解题思路:
dp[i][j]
表示字符串s下标范围[i,j]
的最长回文子序列dp[i][j] = dp[i+1][j-1] + 2
, 左右各加一个元素,长度+2;s[i]
和s[j]
不可能同时作为同一个回文子序列的首尾, dp[i][j] = max(dp[i+1][j], dp[i][j-1])
dp[i][i]=1
, 单个字符肯定是回文字符串,长度为1dp[i][j]=0
,当i>j
时候;则只有当0<=i<=j<n
时,才会有dp[i][j]>=0
代码实现:
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
if n<2:
return 1
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
if(n < 2)
{
return 1;
}
vector<vector<int>> dp(n, vector<int>(n, 0));
for(int i=0; i<n; i++)
{
dp[i][i] = 1;
}
for(int i=n-1; i >= 0; i--)
{
for(int j=i+1; j<n; j++)
{
if(s[i] == s[j])
{
dp[i][j] = dp[i+1][j-1] + 2;
}
else
{
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
};
时间复杂度:O(n^2)
空间复杂度:O(n^2)