上面是一个按照时间段发生的任务a,b,c,d,e,f,g,h，有的任务之间会有时间重叠。定义：
任务j开始于时间 s j s_j sj， 结束时间为 f j f_j fj如果两个任务没有重叠的时间(一个任务的结束时间小于另外一个任务的开始时间)，则两个任务互相兼容
目标：对于每个任务的权重都看作一样的，都一样重要。此时从上述任务中找到最多能互相兼容的任务集合。
从上面可以看到，兼容最多的任务集合是{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 ( n l o g n ) O(nlogn) O(nlogn)
证明：
假设上面是贪心算法，下面是最优解。r时刻以前的两序列一样，下面选择第r+1时刻，如何选取呢？
贪心算法的选取规则就是选择结束时间最早的那个任务，但是其开始时间会比第r时刻的结束时间要晚，这样才不会冲突，然后越早完成任务才能越早去完成下一个任务。
带权区间调度问题
上面是一个按照时间段发生的任务a,b,c,d,e,f,g,h，有的任务之间会有时间重叠。定义：
任务j开始于时间 s j s_j sj， 结束时间为 f j f_j fj如果两个任务没有重叠的时间(一个任务的结束时间小于另外一个任务的开始时间)，则两个任务互相兼容
目标：对于每个任务的权重并不一样，有的任务重要，权重更高一些。此时从上述任务中找到权重最大且互相兼容的任务集合。
带权区间调度问题与不带权调度问题的区别是任务的重要性不一样，不能按照之前的贪心算法按照最后结束时间排序：
比如上面的a,b两个任务，如果按照贪心算法根据结束时间最早的话，应该选择a任务，但a任务的权重仅为1，而任务b权重为999，因此应该选择b任务
那么对于带权区间调度问题应该怎么处理呢？答案是动态规划
解题思路：动态规划
动态规划四步骤确定状态挖掘规律，找到状态转移方程初始条件和边界情况确定计算顺序 确定状态
先将任务按照结束时间排序：
定义状态OPT(j)为任务{1,2,3...,j}的最大权重，那么可以得到：
O P T ( 1 ) = 3 OPT(1)=3 OPT(1)=3 ，任务1自己 O P T ( 2 ) = 3 OPT(2)=3 OPT(2)=3 ，任务2与任务1重叠，找两个任务中权重更大的那个，即任务1 O P T ( 3 ) = 5 OPT(3)=5 OPT(3)=5 ，任务3与任务1，任务2重叠，找三个任务中权重更大的那个，即任务3 O P T ( 4 ) = 5 OPT(4)=5 OPT(4)=5 ，任务4与任务2，3重叠，与1步重叠，有两种选择，第一种任务1和任务4，权重和事5；第二种是任务3，权重为5 O P T ( 5 ) = 8 OPT(5)=8 OPT(5)=8 ，任务5与任务1,2,3,4都重叠，可以找之前的权重最大和，以及它自己，二者两两比较之后确定选择自己任务5，权重为8 O P T ( 6 ) = 8 OPT(6)=8 OPT(6)=8 ，任务6与任务3,4,5重叠，不重叠的有任务1,任务2，任务1+任务6的权重和为6，小于之前的权重和8，因此选择完成任务5，权重为8 O P T ( 7 ) = 9 OPT(7)=9 OPT(7)=9 ，任务7与任务4,5,6重叠，不重叠的有任务1,2,3，从中找出最大的权重和并加上任务7的权重，5+4=9，大于之前的权重和8，因此最终结果为3,7任务，权重和为9 O P T ( 8 ) = 10 OPT(8)=10 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，则 O P T ( j ) = v j + O P T ( P ( j ) ) OPT(j) = v_j + OPT(P(j)) OPT(j)=vj+OPT(P(j))Case2: 如果不选择任务, 则 O P T ( j ) = O P T ( j − 1 ) OPT(j) = OPT(j-1) OPT(j)=OPT(j−1)
则状态转移方程为：
m a x ( v j + O P T ( P ( j ) ) , O P T ( j − 1 ) ) max(v_j + OPT(P(j)), OPT(j-1)) max(vj+OPT(P(j)),OPT(j−1))
初始条件和边界情况O P T ( 0 ) = 0 OPT(0) = 0 OPT(0)=0
完整的状态转移方程为：
确定计算顺序对于上述举例，最优解是OPT(8)，但是由于计算OPT(8)需要计算OPT(7)，所以计算顺序为OPT(1),OPT(2),...,OPT(8)
假如一个问题的状态转移方程为 m a x ( v j + O P T ( P ( j ) ) , O P T ( j + 1 ) ) max(v_j + OPT(P(j)), OPT(j+1)) max(vj+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 f_i fi从小到大排序计算P(j)， 即找到每个任务前面最近的不重叠的任务迭代计算状态方程
排序时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
找P(j)时间复杂度为 O ( n ) O(n) 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 ) O(n) O(n)
自顶向下
使用递归的方式去完成
背包问题
小偷偷东西，但是背包的重量或者体积受限，如何才能使得偷到的东西总价值最多
给定一个背包和n种物品物品j重量为 w j > 0 w_j>0 wj>0和价值 v j > 0 v_j>0 vj>0背包容量为W
目标：使得背包物品总价值最大
贪心算法行不通：
按照价值从小到达排序按重量由大到小排序按价值/重量的比 由大到小排序
如果只是一个限制条件的话，贪心算法是可行的。如果是两个及以上的限制的话，还是要考虑动态规划方法
确定状态转移方程定义OPT(i)是物品1,2,…,i放入背包后的最大价值，那么有下面两种情况
Case 1：不选择物品i， O P T ( i ) = O P T ( i − 1 ) OPT(i) = OPT(i-1) OPT(i)=OPT(i−1)Case 2：选择物品i， O P T ( i ) = v i + O P T ( i − 1 ) OPT(i) = v_i + OPT(i-1) OPT(i)=vi+OPT(i−1)
上述状态方程没有考虑到放入物品后，除了价值增加之外，背包的能够再放入的重量也要减去该物品的重量
因此定义定义OPT(i, w)是物品1,2,…,i放入容量为w背包后的最大价值，那么有下面两种情况
Case 1：不选择物品i， O P T ( i , w ) = O P T ( i − 1 , w ) OPT(i, w) = OPT(i-1, w) OPT(i,w)=OPT(i−1,w)Case 2：选择物品i， O P T ( i , w ‘ ) = v i + O P T ( i − 1 , w − w i ) OPT(i, w^‘) = v_i + OPT(i-1, w-w_i) OPT(i,w‘)=vi+OPT(i−1,w−wi) 初始条件和边界情况
如果i=0， O P T ( i , w ) = 0 OPT(i, w) = 0 OPT(i,w)=0如果w_i > w, O P T ( i , w ) = O P T ( i − 1 , w ) OPT(i, w) = OPT(i-1, w) OPT(i,w)=OPT(i−1,w) 如果物体的重量超过背包能容许放入的重量，那么该物体将不会放入
因此最终的状态转移方程为：
确定计算顺序根据w由小到大，i由小到大计算
自底向上
时间复杂度为 O ( n w ) O(nw) O(nw)
空间复杂度为 O ( n w ) O(nw) O(nw)
基于上面的表可以得到，当w限制为11时候，最优解是拿取商品3和4，总价值是40，总重量是11，满足要求
自顶向下
使用递归的方式，有些地方不需要进行计算
学习视频
https://tianchi.aliyun.com/course/932/14634
贪心算法和动态规划算法是比较巧妙的算法，需要挖掘一些限制条件和状态变换规律
例题 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: O P T ( i ) = O P T ( i − 1 ) + n u m s [ i ] OPT(i)=OPT(i-1) + nums[i] OPT(i)=OPT(i−1)+nums[i]
Case2: O P T ( i ) = n u m s [ i ] OPT(i) = nums[i] OPT(i)=nums[i]
初始条件和边界情况：
O P T ( 0 ) = n u m s [ 0 ] OPT(0) = nums[0] OPT(0)=nums[0]
如果nums为空，则 O P T = N o n e OPT=None OPT=None
其它情况， O P T ( i ) = m a x ( n u m s [ i ] , O P T ( i − 1 ) + n u m s [ i ] ) OPT(i) = max(nums[i], OPT(i-1)+nums[i]) 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& nums) {
int n = nums.size();
vector dp(n+1, 0);
for(int i=0; i
这里有dp空间可以优化的地方，因为只与前面那个有关系，可以用一个变量来保存该值
class Solution {
public:
int maxSubArray(vector& 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
]
t_1[i] == t_2[j]
t1[i]==t2[j]， 则OPT(i, j) = OPT(i-1, j-1) + 1Case2 ：如果
t
1
[
i
]
!
=
t
2
[
j
]
t_1[i] != t_2[j]
t1[i]!=t2[j]， 则考虑两个字符的状态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
]
t_1[i] == t_2[j]
t1[i]==t2[j] else OPT(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> dp(len1+1, vector(len2+1, 0));
for(int i=0; i
时间复杂度：
O
(
m
n
)
O(mn)
O(mn), m，n分别为两字符串的长度
空间复杂度：
O
(
m
n
)
O(mn)
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 动态规划：股票的买卖和背包问题比较相似，都是有一定的条件，本题是求的买入和卖出之间的利润差，以及何时买何时卖的问题。肯定是最低点买入，最高点卖出的时候利润最大：
定义状态：定义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& prices) {
int n = prices.size();
if(n < 2)
{
return 0;
}
vector dp(n, 0);
dp[0] = prices[0];
int res = 0;
for(int i=1; i
由于dp的状态转移方程只与前一个相关，这里可以优化其空间，只用一个变量进行保存即可；
class Solution {
public:
int maxProfit(vector& prices) {
int n = prices.size();
if(n < 2)
{
return 0;
}
int min_val = prices[0];
int res = 0;
for(int i=1; i
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
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 *
1
0
4
10^4
1040 <= prices[i] <=
1
0
4
10^4
104
解题思路：
动态规划：这个与上一题的区别是不限制交易次数，当天能买入和卖出，因此每天有两个状态，买入还是卖出；
定义状态：由于每天有两种状态，因此定义两个dp[i][0]表示第i天手里无股票的利润, dp[i][1]表示第i天手里有一支股票的利润状态转移方程：
d
p
[
i
]
[
0
]
=
m
a
x
(
d
p
[
i
−
1
]
[
0
]
,
d
p
[
i
−
1
]
[
1
]
+
p
r
i
c
e
s
[
i
]
)
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i]) 当天手头无股票的可能情况有两种，前一天就无股票，今天不买入；前一天有股票，今天卖出；
d
p
[
i
]
[
1
]
=
m
a
x
(
d
p
[
i
−
1
]
[
1
]
,
d
p
[
i
−
1
]
[
0
]
−
p
r
i
c
e
s
[
i
]
)
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
dp[i][1]=max(dp[i−1][1],dp[i−1][0]−prices[i]) 当天手头有一支股票的可能情况有两种，前一天就有股票，今天不买入；前一天无股票，今天买入；
初始条件和边界情况：
d
p
[
0
]
[
0
]
=
0
dp[0][0] = 0
dp[0][0]=0 不购买
d
p
[
0
]
[
1
]
=
−
p
r
i
c
e
s
[
0
]
dp[0][1] = -prices[0]
dp[0][1]=−prices[0] 购买 计算顺序： 从小到大
代码实现：
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& prices) {
int n = prices.size();
if(n<2)
{
return 0;
}
vector> dp(n, vector(2, 0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i=1; i
由于dp的关系只与前一项有关系，可以对空间进行优化，使用两个变量来代替二维数组存储相应的结果；
class Solution {
public:
int maxProfit(vector& 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
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
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
]
s[i] == s[j]
s[i]==s[j], 则有dp[i][j] = dp[i+1][j-1] + 2, 左右各加一个元素，长度+2；如果
s
[
i
]
!
=
s
[
j
]
s[i] != s[j]
s[i]!=s[j]，则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=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> dp(n, vector(n, 0));
for(int i=0; i= 0; i--)
{
for(int j=i+1; j
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
参考
上海科技大学CS240算法设计算法导论
