算法：动态规划
动态规划
区间调度问题
无权区间调度问题
上面是一个按照时间段发生的任务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}的最大权重，那么可以得到：
- OPT(1)=3 ，任务1自己
- OPT(2)=3 ，任务2与任务1重叠，找两个任务中权重更大的那个，即任务1
- OPT(3)=5 ，任务3与任务1，任务2重叠，找三个任务中权重更大的那个，即任务3
- OPT(4)=5 ，任务4与任务2，3重叠，与1步重叠，有两种选择，第一种任务1和任务4，权重和事5；第二种是任务3，权重为5
- OPT(5)=8 ，任务5与任务1,2,3,4都重叠，可以找之前的权重最大和，以及它自己，二者两两比较之后确定选择自己任务5，权重为8
- OPT(6)=8 ，任务6与任务3,4,5重叠，不重叠的有任务1,任务2，任务1+任务6的权重和为6，小于之前的权重和8，因此选择完成任务5，权重为8
- OPT(7)=9 ，任务7与任务4,5,6重叠，不重叠的有任务1,2,3，从中找出最大的权重和并加上任务7的权重，5+4=9，大于之前的权重和8，因此最终结果为3,7任务，权重和为9
- OPT(8)=10 ，任务8与任务6,7重叠，不重叠的有任务1,2,3,4,5，从中找出最大的权重和并加上任务8的权重，8+2=10，大于之前的权重和9，因此最终结果为5, 8任务，权重和为10
状态转移方程
定义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)的值有两种情况：
- Case1: 如果选择任务
j，则OPT(j) = v_j + OPT(P(j)) - Case2: 如果不选择任务, 则OPT(j) = OPT(j-1) 则状态转移方程为：max(v_j + OPT(P(j)), OPT(j-1))
初始条件和边界情况OPT(0) = 0
完整的状态转移方程为：
确定计算顺序
对于上述举例，最优解是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是任务的权重
- 首先按照结束时间f_i 从小到大排序
- 计算
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)
- 自顶向下
使用递归的方式去完成
背包问题
小偷偷东西，但是背包的重量或者体积受限，如何才能使得偷到的东西总价值最多
- 给定一个背包和n种物品
- 物品
j重量为w_j>0 和价值v_j>0 - 背包容量为
W
目标：使得背包物品总价值最大
贪心算法行不通：
- 按照价值从小到达排序
- 按重量由大到小排序
- 按价值/重量的比 由大到小排序
如果只是一个限制条件的话，贪心算法是可行的。如果是两个及以上的限制的话，还是要考虑动态规划方法
确定状态转移方程
定义OPT(i)是物品1,2,...,i放入背包后的最大价值，那么有下面两种情况
- Case 1：不选择物品
i，OPT(i) = OPT(i-1) - Case 2：选择物品
i，OPT(i) = OPT(i-1)
上述状态方程没有考虑到放入物品后，除了价值增加之外，背包的能够再放入的重量也要减去该物品的重量
因此定义定义OPT(i, w)是物品1,2,...,i放入容量为w背包后的最大价值，那么有下面两种情况
- Case 1：不选择物品
i，OPT(i, w) = OPT(i-1, w) - Case 2：选择物品
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由小到大计算
自底向上
- 时间复杂度为O(nw)
- 空间复杂度为O(nw)
基于上面的表可以得到，当w限制为11时候，最优解是拿取商品3和4，总价值是40，总重量是11，满足要求
自顶向下
使用递归的方式，有些地方不需要进行计算
贪心算法和动态规划算法是比较巧妙的算法，需要挖掘一些限制条件和状态变换规律
例题
46 最大子数组和
给你一个整数数组 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) 的解法，尝试使用更为精妙的 分治法 求解。
解题思路
- 滑动窗，定义一个left，right滑动窗，往右滑动，如果发现此时窗口的值比之前的窗口值要小的话，右指针继续往右移动，如果left指向的元素是一个负数，left指针可以右移
- 动态规划：定义
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个数结尾的连续子数组的最大和 - 状态转移方程：
- Case1:OPT(i)=OPT(i-1) + nums[i]
- Case2:OPT(i) = nums[i]
- 初始条件和边界情况：
- OPT(0) = nums[0]
- 如果nums为空，则OPT=None
- 其它情况，OPT(i) = max(nums[i], OPT(i-1)+nums[i])
- 确定计算顺序：从小到大计算
代码实现
- python实现
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)
- c++实现
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;
}
};
459 最长公共子序列
给定两个字符串 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 <= 1000text1和text2仅由小写英文字符组成。
解题思路：
- 暴力法：每个元素比对的时候都与另外一个字符串比较一下，判断是否有相同元素以及位置前后
- 动态规划：定义
OPT(i, j)代表字符串t1[0:i]和字符串t2[0:j]的最长公共子序列的长度
动态规划：
- 定义状态：定义
OPT(i, j)代表字符串t1[0:i]和字符串t2[0:j]的最长公共子序列的长度 - 状态转移方程：
- Case1 ：如果t_1[i] == t_2[j] ， 则
OPT(i, j) = OPT(i-1, j-1) + 1 - Case2 ：如果t_1[i] != t_2[j] ， 则考虑两个字符的状态
OPT(i, j) = max(OPT(i-1, j), OPT(i, j-1))
- Case1 ：如果t_1[i] == t_2[j] ， 则
- 初始条件和边界条件：
OPT(0, j) = OPT(i, 0) = 0初始化行与列OPT(i, j) = OPT(i-1, j-1) + 1if t_1[i] == t_2[j] elseOPT(i, j) = max(OPT(i-1, j), OPT(i, j-1))
- 确定计算顺序：
i,j从小到大计算
=
代码实现
- python实现
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]
- c++实现
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)
104 买卖股票的最佳时机
给定一个数组 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 <= 1050 <= prices[i] <= 104
解题思路：
- 暴力法：在满足
i<j的情况下，找max(prices[j]-prices[i]) - 动态规划：股票的买卖和背包问题比较相似，都是有一定的条件，本题是求的买入和卖出之间的利润差，以及何时买何时卖的问题。肯定是最低点买入，最高点卖出的时候利润最大：
- 定义状态：定义
dp[i]表示前i天的最小值 - 确定状态转移方程：第
i+1天的价格减去前i天的最小值就是利润。并更新最小值 - 初始条件和边界：初始时最大收益为0，第一天的最小值为
prices[0] - 确定计算顺序：从小到大计算
- 定义状态：定义
代码实现
- python实现
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
- c++实现
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)
105 买卖股票的最佳时机II
给定一个数组 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。
提示：
- 1 <= prices.length <= 3 *10^4
- 0 <= prices[i] <=10^4
解题思路：
- 动态规划：这个与上一题的区别是不限制交易次数，当天能买入和卖出，因此每天有两个状态，买入还是卖出；
- dp[0][0] = 0
不购买
- dp[0][1] = -prices[0]
购买
- 初始条件和边界情况：
- 计算顺序：从小到大
- 定义状态：由于每天有两种状态，因此定义两个
dp[i][0]表示第i天手里无股票的利润,dp[i][1]表示第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]) 当天手头有一支股票的可能情况有两种，前一天就有股票，今天不买入；前一天无股票，今天买入；
代码实现：
- python实现
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] # 手里无股票的时候利润肯定是最大的
- c++实现
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)
277 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
解题思路：
- 假设一个字符串是回文序列的话，两边各减去一个元素仍然是回文串
- 定义状态：
dp[i][j]表示字符串s下标范围[i,j]的最长回文子序列 - 状态转移方程:
- 如果s[i] == s[j] , 则有
dp[i][j] = dp[i+1][j-1] + 2, 左右各加一个元素，长度+2； - 如果s[i] != s[j] ，则
s[i]和s[j]不可能同时作为同一个回文子序列的首尾,dp[i][j] = max(dp[i+1][j], dp[i][j-1])
- 如果s[i] == s[j] , 则有
- 初始条件和边界情况：
dp[i][i]=1， 单个字符肯定是回文字符串，长度为1dp[i][j]=0，当i>j时候；则只有当0<=i<=j<n时，才会有dp[i][j]>=0
- 计算顺序：基于状态转移方程，从大到小计算
代码实现：
- python实现
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]
- c++实现
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)
参考
- 上海科技大学CS240
- 算法设计
- 算法导论