1. 最长上升子序列
数组存储信息含义：
arr[i] 存储以第i个数字结尾的最长上升序列的长度f(i)。
转移关系
使用递推的思考还是归纳式的思考比较好？
若序列
s
s
s以第k+1个数字结尾的话，目前已有arr[0]、arr[1]、…、arr[k];
arr[k+1]的计算：将nums[k+1]放在以nums[j]结尾的最长上升序列后，其中需要满足(
j
≤
k
且
n
u
m
s
[
j
]
≤
n
u
m
s
[
k
+
1
]
j\leq k 且 nums[j] \leq nums[k+1]
j≤k且nums[j]≤nums[k+1])，所得到的以nums[k+1]结尾的最长上升序列。
迭代更新公式
f ( i ) = { 1 i = 0 m a x ( f ( 0 ) , f ( 1 ) , . . . , f ( j ) , . . . , f ( i − 1 ) ) + 1 n u m s [ j ] < n u m s [ i ] f(i) = \begin{cases} 1 & i=0 \\ max( f(0), f(1), ..., f(j), ..., f(i-1))+1 & nums[j]<nums[i] \end{cases} f(i)={1max(f(0),f(1),...,f(j),...,f(i−1))+1i=0nums[j]<nums[i]
2. 最长公共子序列
数组存储信息含义：
arr[i][j] 存储第一个文本的前i个字符与第二个文本的前j个字符(两个子串)的最长公共子序列
转移关系
也可以根据最后一个字符是否在公共子串中进行分类。
已有题解的描述
对于arr[m] [n],比较str1[m]与str2[n]是否相同:
如果相同，则查看第一个文本的前m-1个字符和第二个文本的前n-1个字符的最长公共子序列。$arr[m] [n] = arr[m-1] [n-1]+1 $
如果不同，则查看第一个文本的前m个字符和第二个文本的前n-1个字符的最长公共子序列 与 则查看第一个文本的前m-1个字符和第二个文本的前n个字符的最长公共子序列；选择两者中的大的。$arr[m] [n] = max( arr[m-1] [n], arr[m] [n-1] ) $
实际思考上的分析
设最长公共子串为s，根据str2[n]是否在s中分为两种情况考虑。
-
如果str2[n]不在s中，则最长公共子串也是(str1, str2[:n-1])的最长公共子串
-
如果str2[n]在s中，在str1从后向前找到等于str2[n]的字符：但是需要查找的复杂度。
如果str1[m] ==str2[n]，则查找 (str1[:m-1], str2[:n-1])的最长公共子串，并附加上该字符
如果str1[m]!=str2[n]，则查找（str1[m-1], str2[n])的最长公共子串
可以分析知道，如果情况1成立，则一定有str1[m] != str2[n];
整理后为题解的表述。
迭代更新公式
f ( m , n ) = { 0 m = 0 或 n = 0 f ( m − 1 , n − 1 ) + 1 s t r 1 [ m ] = s t r 2 [ n ] m a x ( f ( m − 1 , n ) , f ( m , n − 1 ) ) s t r 1 [ m ] ≠ s t r 2 [ n ] f(m,n) = \begin{cases} 0 & m=0或n=0 \\ f(m-1,n-1)+1 & str1[m]=str2[n] \\ max( f(m-1,n), f(m,n-1) ) & str1[m]\neq str2[n] \end{cases} f(m,n)=⎩⎪⎨⎪⎧0f(m−1,n−1)+1max(f(m−1,n),f(m,n−1))m=0或n=0str1[m]=str2[n]str1[m]=str2[n]
相关问题
- 最长公共子序列的个数？
- 有哪些最长公共子序列（字符串）
- 如果是三个字符串呢？
3. 爬楼梯
经典动态规划
数组存储信息含义：
MinCost[i]存储爬到第i阶楼梯的最小花费。
转移关系
爬到第i个楼梯所需要的花费是前两个楼梯的最小花费+当前楼梯所需要的花费
迭代更新公式
M i n C o s t [ i ] = M i n ( M i n C o s t [ i − 1 ] , M i n C o s t [ i − 2 ] ) + c o s t [ i ] MinCost[i] = Min(MinCost[i-1],MinCost[i-2])+cost[i] MinCost[i]=Min(MinCost[i−1],MinCost[i−2])+cost[i]
M i n C o s t [ i ] = { c o s t [ i ] i = 0 , 1 m i n ( M i n C o s t [ i − 1 ] , M i n C o s t [ i − 2 ] ) + c o s t [ i ] i ≥ 2 MinCost[i] = \begin{cases} cost[i] & i=0,1 \\ min(MinCost[i-1], MinCost[i-2])+cost[i] & i \ge 2 \end{cases} MinCost[i]={cost[i]min(MinCost[i−1],MinCost[i−2])+cost[i]i=0,1i≥2
4. 模：购物列表
0-1 背包
购物列表中每个物品是否购买，共有2^n种组合
每个物品作为外循环，不断更新dp
数组存储信息含义：
dp[i] : 对于前k个物品，加个取模为i 对应的最大金额数。
dp[1]: 对于前k个物品，买或不买，总金额取模后余1的最大金额数。
转移关系：
对于当前遍历物品k+1, 价格为 w k + 1 w_{k+1} wk+1
n e x t _ d p [ i ] = m a x ( d p [ i ] , d p [ M O D − w k + 1 % M O D ] + w k + 1 ) next\_dp[i] = max( dp[i], dp[ MOD-w_{k+1}\% MOD] + w_{k+1} ) next_dp[i]=max(dp[i],dp[MOD−wk+1%MOD]+wk+1)
其中 n e x t _ d p [ i ] next\_dp[i] next_dp[i]表示前k+1个物品对应，总金额取模后为i的最大金额数
5. 有限人数：执行任务选择，获取利益
0-1 背包
根据每个人数是否执行，共有2^n种组合方式。
每个任务作为外循环，不断更新dp
数组存储信息含义：
dp[i][j] 使用i个人，获得收益j的种数
dp[0][0] 取1 没人干活取得0收益；部分位置为不存在或不合理，取0
转移关系：
输入：pre[i][j] 和 新任务( 需要m人，产生n利益 )
输出：curr[i][j]
c u r r [ i ] [ j ] = p r e [ i − m ] [ j − n ] + p r e [ i ] [ j ] curr[i][j] = pre[i-m][j-n] + pre[i][j] curr[i][j]=pre[i−m][j−n]+pre[i][j]
可能会要求取模；
根据问题约束条件的个数来确定dp使用存储数据的矩阵维度